All ways to build a notional from lot sizes

Question

You can trade in a fixed set of lot sizes, each usable any number of times. List every distinct combination of lots that sums exactly to a target notional. Combinations are unordered, so [2, 3, 3] and [3, 2, 3] are the same and should appear once.

denoms = [2, 3, 5], target = 8
-> [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Return all combinations summing to the target, with unlimited reuse and no duplicates.

Accepted Answer

Backtrack with a start index, but recurse into the same index rather than the next one so a lot size can be reused. Passing start forward (never backward) guarantees non-decreasing combinations, which eliminates reorderings. Sorting the denominations lets you break as soon as a lot exceeds the remaining notional. Tracing [2, 3, 5], target 8: the branch of all 2s gives [2,2,2,2]; starting with a 3 gives [2,3,3] and later [3,5]. Time is output-sensitive (proportional to the number of combinations times their length), space O(target) recursion depth. Edge cases: target 0 yields one empty combina…

All ways to build a notional from lot sizes

Your answer

More Coding questions