Yes! The trick is to count each input with its effective value rather than its nominal value.
Transactions are composed of three parts: the overhead, the inputs and the outputs.
Outputs:
The size of the output scripts is determined by the recipient addresses, so their size is given by the transaction instructions. We do not know whether we will need a change output yet, but we know what size it would be if we created one.
Overhead:
The transaction overhead is 10 bytes for non-segwit transactions, or 42 WU for segwit transactions. You can probably guess which one you'll need, but in the worst case you overestimate by 0.5 vB. We can therefore consider the overhead size also to be fixed.
Inputs:
The tricky part is the transaction inputs. You do not know how many you will need, and might not know what input script sizes they'll have if you have inputs of various address formats. Additionally, signatures are not always the same size. However, we do know the maximum size of the signature, and the size of the input script for each UTXO. Together with the target fee rate, we can calculate the effective value:
effectiveValue = utxo.value − feePerByte × bytesPerInput¹
The selection target starts out as the sum of the recipient amounts. We simplify the coin selection problem by adding the fixed costs to the selection target. We then perform the selection via counting effective values rather than nominal values. Since each input has paid for itself already when it is selected, we no longer need to worry about an input's fee impact after selection; instead each effective value goes fully towards the selection target.
In regard to the change output, there are two strategies. One, if you are aiming to build a transaction that avoids creating change, e.g. by using Branch and Bound selection, you keep the target as is: target = recipient amounts + fees for fixed transaction parts. Two, if you are using a strategy that will create change, you add a buffer to the selection target that is large enough to cover the fee of the change output and leave enough for a good-sized change output: target = recipient amounts + fees for fixed tx parts + change output cost + minChange.
For the signatures, you estimate using the maximum signature length. Since the signatures are part of the witness for segwit inputs, this results only in a small size overestimation which will lead to minutely overshooting the target fee rate.² Alternatively, you can use signature grinding to save an expected 0.5 bytes per signature and estimate the fee rate more precisely.
¹ Effective value was proposed in section 5.3 of An Evaluation of Coin Selection Strategies, Erhardt 2016, disclosure: authored by yours truly.
² Overshooting the target fee rate is preferable; it costs only a few satoshis and slightly increases the priority of the transaction. Undershooting the target fee rate is problematic, since some payment processors require a minimum fee rate to accept a payment and falling below the default minRelayTxFeeRate can prevent a transaction from relaying altogether.
