subset sum

[geegoo!]

hallo reader,
im having a problem concerning recursion in C++. I ve encountered a problem that requires to find all the subsets of a set of intergers that gives a required sum, meaning..
Enter integers: 16, 3,3,13.
Required sum: 19
The prog should output:
16+3=19
13+3+3=19
the maximum size of the array is 20. i want to out allll the susbsets that their sume is equal to that required sum entered by the user..i cant think of an algorithim but i have some ideas of what should be done;
1) the array(or a linked list) should be sorted ascendingly
2) a friend of mine suggested using stacks but i dnot know how to do it exactly..
2) the no. of subsets is equal to 2^n, while n is the no. of elements entered by the user.(maximum no. of subsets is 2^20)
3) the no . of each subset is found by combinations .
thats all ..please if you have an idea of how to solve this prob by recursion you will make my day!!

[jwenting]

why would you use recursion here at all?
I don't see the reason for it.

[1o0oBhP]

if you sort it DESCENDING you can loop through the array subbing the element from the total sum, if the next element causes the result to fall below zero you skip it for example

sum = 15
integers: 10, 4, 3, 1

we loop through and take 10 from 15 leaving 5
take 4 from 5 leaving 1
take 3 from 1 leaving -2 : skip it
take 1 from 1 leaving 0 : stop on zero

result = 10+4+1 = 15

Hope this helps :)

[1o0oBhP]

post any code you get from my algorithm, it would be interesting to see how you did it

[1o0oBhP]

PS: I can see a recursion method as i havent given you the full algorithm i came up with. ill leave it up to you to see if you can get the rest of the algo ;)

[bleach.kenpachi]

Hey Guys i m also finding the same problem
One soln i have in mind is
iterating through the array and checking sum of 2 numbers, 3 numbers,4 numbers and so on until end of array.
But the problem is that how many for loops i should run as array size is not predetermined.
So i need to think of a particular function for it.
Plz provide ur suggestions

[jim_thomas]

Here is a recursive solution - ill post the code, then explain what is going on. Also, this is code I wrote for brute forcing a knapsack cipher, so there is a little more going on then is necessary to understand (the whole set bit business.)

int set_bit(int solution, int bit)
{
    int a = (1 << bit);
    return (solution+a);
}
//the int returned by subset sum has the bit values set to the solution
// if -1, there was no solution
int subset_sum(int s, int a_index, int solution)
{
    //to do - make bits work right
    //we need a successful add to make bits on the left side

    if (s <0)
        return -1;
    if (s == 0)
        return solution;
    if (a_index == 16)
        return -1;
    int included = subset_sum( s - hard[a_index], a_index+1, set_bit(solution, a_index) );
    int not_included = subset_sum( s - hard[a_index], a_index+1, solution );

    if (included >= 0)
        return included;
    return not_included;
}

**explanation time:
The subset_sum function takes a target sum and the current place in our array, a_index. the solution to the subset sum problem is:
1) include the current item in our solution - the solution is the sum minus the current item, plus the solution to the rest of the array.
2) do not include the current item in our solution - the solution is the solution to the sum and rest of the array

base cases: we included an item that made the sum negative, return -1
we ran out of array and did not meet the sum, return -1
we have met the sum, return solution.

in my code, solution is a 16 bit integer, where each one represents include the item. ie 7 = 00000111, the last 3 items made the solution.

[Srcee]

if you sort it DESCENDING you can loop through the array subbing the element from the total sum, if the next element causes the result to fall below zero you skip it for example

sum = 15
integers: 10, 4, 3, 1

we loop through and take 10 from 15 leaving 5
take 4 from 5 leaving 1
take 3 from 1 leaving -2 : skip it
take 1 from 1 leaving 0 : stop on zero

result = 10+4+1 = 15

Hope this helps :)

This is no good for the next array: 10 4 3 2

[jt9]

There is definitely a bug i left in this code! I'm sorry - the
int not_included = subset_sum( s - hard[a_index], a_index+1, solution );

should be
int not_included = subset_sum( s , a_index+1, solution );

This may solve your issue with the code. If it doesnt, check that you are intializing the a_index before the recursive call to the size of your vector - if i recall i had a vector of size 16 to solve. so you will need to set the
if (a_index == 16)

to
if (a_index == 4)

as well. overall though, the idea with the code isn't necessarily to cut and paste it, but to use it to understand the problem. apologies for the bug as well!

[Bajeed]

Here is the solution for the Maximum sum of a subset in an array
http://bajeed.blogspot.com/2010/07/program-to-find-maximum-sum-of-subset.html

[now how abt tht]

if you sort it DESCENDING you can loop through the array subbing the element from the total sum, if the next element causes the result to fall below zero you skip it for example

what if u have:
sum=14
integers : 10 5 -1

then it gives false that sum of 14 cannot be got!

because 14-10=4
4-5 = -1
hence return false

but 10+5-1=14