Subset sum problem... no idea how

[scheppy]

Good Day

Lets say i have a array of integers....
-always differs in length

I need to know all the possibilities the numbers in the string have to add up to a certain number.
let say 5;
and my array contains 1,3,4,3,5,8,2,1;

than the possibilites would be.... (3,2)(4,1)(3,1,1)

But i also need to know the index which they where gotten from..... for tracking purposes.
Also, since thier are 2 possibilites of 3,2, it would have to used the last 3 that it find..... this case it would be 3 from the 3rd index, and 1 from index 0, and next 1 from index 7;

Could anyone help me with this?

Thanks
Scheppy

[JamesCherrill]

Hi Scheppy

Picking an unknow number of entries from an array of unknown length - you will have problems coding this with ordinary loops because you won't know how many loops to code. It has "recursion" written all over it. Eg

array contains 1,3,4,3,5,8,2,1, target is 5

   take the 1, array now contains 3,4,3,5,8,2,1, target is now 4
   target is >0, recurse to find solution in the remainder of the array
      take the 3, array contains 4,3,5,8,2,1, target is now 1
         take the 4, - target exceeded, go no further
         take the 3, - target exceeded, go no further
         take the 5, - target exceeded, go no further
         take the 8, - target exceeded, go no further
         take the 2, - target exceeded, go no further
         take the 1, - target met - we have a solution!
   take the 3, array now contains 4,3,5,8,2,1, target is now 2
        ...

Note: when you hit the target, record the indexes (you can worry about that when you have working code that finds the required values)

Think about that... if still stuck come back here for some more hints.
JC

[vitaquous]

Not sure I understand, it sounds like you are attempting to loop through your array and find all the combinations that add to a certain sum IE 5.
Plus you would like to have the index of each element of the array used to obtain 'sum' your array being 1,3,4,3,5,8,2,1

Why would you not loop through this array, add each to the if === 5 great if < 5 continue if > 5 do not include that element in second array that will hold indexes of all elements used to add to 'sum' Once you have the first 'sum' save second array and begin again at the start of orignial array 1,3,4,3,5,8,2,1 with each element used in previous successful addition to 'sum' popped ie 3,4,3,5,8,2 (1,3,1 popped)

You would only need two arrays to accomplish this the original and a second that you store the indexs in with a delimiter you place to seperate indexs. IE [1,3,1,'^',3,2,'^',]

[JamesCherrill]

If you pop all the numbers used in a sucessful sum then you will not be abl to use any of those numbers in any other solution, eg with 2,3,2,1 you will find 2,3 then pop those values leaving 2,1 and thus never find the 2,2,1 solution.
This problem requires you to traverse all possible subsets of the array with pruning of branches that meet or exceed the target. Traverse all subsets can be done without recursion, but recursion is by far the cleanest approach.