What is the coin selection algorithm? When creating a transaction in the standard client, what is the algorithm used to determine which unspent outputs will be used as inputs?

Has this changed since the first version? What different algorithms are used by alternative clients?

Does the client make any attempt to optimize which 'coins' are used based on minimizing the transaction size, the resulting fragmentation, or the 'age' of the coins (value/transactions) used as the source?
I couldn't find the results of the Coin Selection written out anywhere, and just finished piecing it together from the code. It works as David mentioned, but here are more details.

The Coin Selection Algorithm logic to transfer Target amount


If any of your UTXO² matches the Target¹ it will be used.
If the "sum of all your UTXO smaller than the Target" happens to match the Target, they will be used. (This is the case if you sweep a complete wallet.)
If the "sum of all your UTXO smaller than the Target" doesn't surpass the target, the smallest UTXO greater than your Target will be used.
Else Bitcoin Core does 1000 rounds of randomly combining unspent transaction outputs until their sum is greater than or equal to the Target. If it happens to find an exact match, it stops early and uses that.
Otherwise it finally settles for the minimum of 


the smallest UTXO greater than the Target
the smallest combination of UTXO it discovered in Step 4.



As David mentioned, the subset problem will first restrict to UTXO that have at least one confirmation if sent by yourself, or six confirmations if received from another wallet, then later relaxes these requirements in two further passes if no suitable set of UTXO could be discovered.



Some examples

Alice has four UTXO:
• UTXO_A 0.1BTC
• UTXO_B 0.3BTC
• UTXO_C 0.5BTC
• UTXO_D 1BTC

I will be ignoring transaction fees for simplicity's sake.

Example 1:

Alice wants to send 0.3BTC.
Bitcoin Core discovers that UTXO_B matches the Target, and it only uses UTXO_B as input.

Example 2:

Alice wants to send 0.4BTC.
Bitcoin Core finds that UTXO_C is the smallest UTXO greater than the Target, and that the sum of all UTXO smaller than the target (i.e. UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4) matches the Target here. Both UTXO_A and UTXO_B are used as inputs.

Example 3:

Alice wants to send 0.45BTC.
Bitcoin Core finds that UTXO_C is the smallest UTXO greater than the Target, and that the sum of all UTXO smaller than the target (i.e. UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4) does not surpass the Target. UTXO_C is used as the sole input, being the next smallest input greater than the Target.

Example 4:

Alice wants to send 0.35BTC.
Bitcoin Core finds that UTXO_C is the smallest UTXO greater than the Target, and that the sum of all UTXO smaller than the target (i.e. UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4) does not match the Target. It adds up randomly selected UTXO 1000 times until they surpass the Target, remembering the smallest sufficient combination. The smallest sufficient combination is then compared with the smallest single input greater than the target. Assuming that it does find the best combination here which would be UTXO_A + UTXO_B, it finds that Target &lt; UTXO_A + UTXO_B &lt; UTXO_C and uses UTXO_A and UTXO_B as inputs.

Example 5:

Alice wants to send 0.6BTC.
Bitcoin Core finds that UTXO_D is the smallest UTXO greater than the Target, and that the sum of all UTXO smaller than the target (i.e. UTXO_A + UTXO_B + UTXO_C = 0.1 + 0.3 + 0.5 = 0.9) does not match the Target. It starts trying random combinations as before, and in this situation would probably discover that UTXO_A + UTXO_C = Target. As it finds a combination that matches the Target, it breaks and immediately goes with that combination. UTXO_A and UTXO_C are used as inputs.



¹"Target" is used here for the amount to be spent.
²UTXO = Unspent Transaction Output