1
$\begingroup$

I want to find a way to generate sets that contain elements that sum to a certain target. Initially, I have an array that contains elements representing the maximum value that can be stored in that index.

For example, the input is [8,6,1] and the target is 10. The algorithm should produce all sets that have elements [ (<=8), (<=6), (<=1) ] such that their sum is equal to 10. Examples include: [8,1,1], [8,2,0], [7,3,0], ...

A major consideration for this algorithm is that it should work on any input length (the above example has a length of 3).

I think the solution is close to the subset sum problem, but I wasn't able to figure it out. Any help is appreciated.

Side note: python code is preferred, but Pseudo-code should be fine.

Thanks

$\endgroup$
1
$\begingroup$

Where subset sum takes exponential time to find a solution, here you can find one solution quickly, but there are exponentially many solutions, and therefore it will take exponential time to find them all.

Or factorial really, on the length (let's call this $n$) of the array, as every time you have a set of $n$ numbers that add up to the target, all $n!$ permutations of this is a solution in the worst case, when they are within the maximum values (that is, [6,4,0] and [4,6,0] are not the same solution but both valid). So if the target can be summed from $n$ numbers in $k$ different ways, then we can have up to as many as $k * n!$ solutions in the worst case.

For small problems, you should be able to solve this using recursion. Here is a pseudocode representation that should work. Hope it all makes sense.

Pseudocode:

1:$\quad$ function RECURSE( index , sum , value , array )

2:$\quad\quad$ sum $\leftarrow$ sum + value

3:$\quad\quad$ if sum = target and index is last index in array then print result $\quad$// it's a match

4:$\quad\quad$ if sum $\gt$ target or index is the last index in array then return $\quad$// no result here

5:$\quad\quad$ increment index

6:$\quad\quad$ for $i = 0$ to $i =$ max allowed value on index do

7:$\quad\quad\quad$ newArray $\leftarrow$ copy of array

8:$\quad\quad\quad$ newArray[index] $\leftarrow i$

9:$\quad\quad\quad$ RECURSE( index , sum , i , newArray )

10:$\quad\quad$ end for

11:$\quad$ end function

$\\$

12:$\quad$ function MAIN

13:$\quad\quad$ for $i = 0$ to max allowed value on index 0 i array do

14:$\quad\quad\quad$ array $\leftarrow$ new array

15:$\quad\quad\quad$ array[0] $\leftarrow$ $i$

16:$\quad\quad\quad$ call RECURSE( 0 , 0 , $i$ , array )

17:$\quad\quad$ end for

18:$\quad$ end function

$\endgroup$
  • $\begingroup$ It looks like the RECURSE function doesn't call itself, so it isn't actually recursive. Have you tested your algorithm? $\endgroup$ – HEKTO Sep 19 at 4:01
  • $\begingroup$ Oops, yes you are right. I did make a working implementation in C#, just forgot the - obviously very important - call to recurse in the pseudocode. It's now added to line 9. Thanks for finding that mistake. $\endgroup$ – AstridNeu Sep 19 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.