'Calculating a list of valid combinations
So I came up with a problem that I can’t logically solve. I’ve fleshed out an example; You have a list of numbers that you need to output (e.g. 3x number 1 & 2x number 2) - we’ll call them ‘target numbers’.
You’re also given a range of source numbers (e.g. 2, 3, 4 and 5).
The task is to return all valid combinations of the source numbers that would allow you to produce the target numbers. You can use any combination and quantity of source numbers.
The constraints are that you can break a source number down to get to target numbers (e.g. you could break down a 5 into a 2 and a 3) but you cannot add source numbers together to get to a target number (for example you can’t add a 1 to a 1 to get to a 2).
Remainders are perfectly acceptable (e.g. using a source 3 to get to a target 2 and the remaining 1 is part of the combination but not ‘used’ in getting to the target).
In the interests of limiting results you’d also want to have a constraint that an acceptable combination does not contain any ‘totally unused’ source numbers [i.e. neither a result of being split nor a target number in the result)
So in the example target & source numbers given, the following results would be valid; [1,1,1,2,2],[3,4],[3,3,1],[4,4] But a [1,1,1,1,1,2] would not be valid, because you cannot join two source 1’s together to make a target 2.
I’ve thought about this logic and am largely thinking the solution involves some level of recursion, but the only examples I’ve seen are where the constraints are reversed (i.e. you can add source numbers together to reach a target number, but cannot split them to reach one)
What kind of logic would you use to generate all valid permutations in code?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|