Printable View
How do you write a recursive algorithm for finding all the subsets of a given number:
i.e if 2 is entered it should give
1,2,12
and if it is 3
1,2,3,12,13,23,123
It has to be recursive and has you are allowed to use only 1 iteration. I know how do do this non-recursively but I'm not sure how to do it recursively.
BTW this is a console application.
Thanks for your help!
how do you do it without recursion? My best guess is that if you know how to do it, you only need to modify the control structure of such a program to use recursion.
Show us what you have, maybe then you'll get a hint on how to go further.
Richard
My "all-subsets" approach has always been to assign each element to a bit, and then just count upwards to 2^n-1, using the binary representation to select elements.
That's not recursive, though.
Well I haven't coded it using iteration but here's an explanation on how to do it:
For a set size of 1 print all numbers upto n seperately. For set size 2, print 1 value and first value +1 then first value +2 until the end of n. then make first value , the previous first value +1 and repeat until first value is 1 less than n.
You doa similar thing for set size 3.
How do you code this recursively?
Lindley: Thats the problem. It has to be done recursively. I understand the recursive relationship I just can't code it.
Recursive relationship:
You have to recurse on size-1 and then iterate each with a number in front. i.e.
for an input of size 5, the size 2 array will be:
12
13
14
15
23
24
25
34
35
45
the size 3 array will be:
123
124
125
134
135
145
234
235
245
345
The only change is the first number in each of the lines, but I cant exactly figure out how to write the algorithm.