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!!
geegoo!
0
Newbie Poster
Recommended Answers
Jump to Postwhy would you use recursion here at all?
I don't see the reason for it.
Jump to Postif 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, 1we loop through and take 10 …
Jump to Postpost any code you get from my algorithm, it would be interesting to see how you did it
All 10 Replies
jwenting
1,889
duckman
Team Colleague
1o0oBhP
4
Posting Pro in Training
1o0oBhP
4
Posting Pro in Training
1o0oBhP
4
Posting Pro in Training
bleach.kenpachi
0
Newbie Poster
jim_thomas
0
Newbie Poster
Srcee
0
Junior Poster in Training
jt9
0
Newbie Poster
Bajeed
0
Newbie Poster
now how abt tht
0
Newbie Poster
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.