It says here https://github.com/bitcoin/bitcoin/blob/master/src/wallet/wallet.cpp#L2458 that to choose coins for a transactions we need to solve subset sum. But subset sum is when you're not allowed to go over a certain amount; whereas in bitcoin you can go over the amount and give change. So why is this necessary?
There are a few goals of coin selection.
Firstly, we want to select enough coins for the user. Secondly, we want to minimize transaction fees. Lastly we want to reduce the UTXO set.
Reducing the UTXO set requires creating less outputs than there are inputs in a transaction. By solving the subset sum problem, we can avoid making a change output and thus help to reduce the UTXO set.