Sets Problem

[inevitable]

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!

[Richard.J]

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

[Lindley]

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.

[inevitable]

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.