-1

This should be a quite simple problem, but I don't have proper algorithmic training and find myself stuck trying to solve this.

I need to calculate the possible combinations to reach a number by adding a limited set of smaller numbers together.

Imagine that we are playing with LEGO and I have a brick that is 12 units long and I need to list the possible substitutions I can make with shorter bricks. For this example we may say that the available bricks are 2, 4, 6 and 12 units long.

What might be a good approach to building an algorithm that can calculate the substitions? There are no bounds on how many bricks I can use at a time, so it could be 6x2 as well as 1x12, the important thing is I need to list all of the options.

So the inputs are the target length (in this case 12) and available bricks (an array of numbers (arbitrary length), in this case [2, 4, 6, 12]).

My approach was to start with the low number and add it up until I reach the target, then take the next lowest and so on. But that way I miss out on the combinations of multiple numbers and when I try to factor that in, it gets really messy.

zkwsk
  • 1,960
  • 4
  • 26
  • 34
  • 1
    What is wrong about this question that it deserves a down vote? – yizzlez Jun 12 '14 at 01:45
  • 1
    Maybe similar to http://stackoverflow.com/questions/3420937/algorithm-to-find-which-number-in-a-list-sum-up-to-a-certain-number – Bharat Jun 12 '14 at 13:33
  • @awesomeyi I can only guess, but... The approach OP gave is pretty much exactly what you need to do - without code or pseudo-code, we can only guess where OP is going wrong ... not to mention that there are quite a few list-all-subset questions here. – Bernhard Barker Jun 12 '14 at 14:34
  • Hi guys, must admit it might not be my best researched question. I did look through some of the existing threads but was not able to find my exact problem, but the link above is pretty spot on except for the fact that it does not return the sets, but the number of possible combinations. – zkwsk Jun 16 '14 at 22:37
  • Possible duplicate of [Algorithm to find which number in a list sum up to a certain number](https://stackoverflow.com/questions/3420937/algorithm-to-find-which-number-in-a-list-sum-up-to-a-certain-number) – sds Jul 25 '18 at 21:53

1 Answers1

1

I suggest a recursive approach: given a function f(target,permissibles) to list all representations of target as a combination of permissibles, you can do this:

def f(target,permissibles):
  for x in permissibles:
    collect f(target - x, permissibles)

if you do not want to differentiate between 12 = 4+4+2+2 and 12=2+4+2+4, you need to sort permissibles in the descending order and do

def f(target,permissibles):
  for x in permissibles:
    collect f(target - x, permissibles.remove(larger than x))
sds
  • 58,617
  • 29
  • 161
  • 278
  • Thanks for your suggestion. Unfortunately I'm not a Python guy, so even though you example seems clear I'm confused about what 'collect' does? If you are able to translate it to ruby, that would be super helpful, but otherwise collect is the only part I don't get. – zkwsk Jun 16 '14 at 22:34
  • I don't know Ruby; my code is not Python. Collect means put the value into an accumulator and return its content on exit from function. – sds Jun 16 '14 at 22:40
  • Great, thanks. I'll see if I can replicate it in Ruby. What language was your example written in, then? – zkwsk Jun 16 '14 at 22:59