# Sets Problem

• 04-03-2008
inevitable
Sets Problem
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.

• 04-03-2008
Daved

What do you think you should recurse on? What should be your stopping point?
• 04-03-2008
inevitable
I realized 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 changes are the numbers in bold, but I cant exactly figure out how to write the algorithm. The stopping point is going to be size one.
• 04-03-2008
nepper271
I believe you should do your recursion as:
1 - The subsets of n are all subsets of n - 1, and all subsets of n - 1, each increased by the element n.
ex:
Code:

```P(2) = { O, {1}, {2}, {1,2} } P(3) = { O, {1} , {2} , {3} , {1,2} , {1,3} , {2,3} , {1,2,3} }  = { O, {1}, {2}, {1,2} } U { OU{3}, {1}U{3}, {2}U{3} , {1,2}U{3} }```
where O is the empty set, and U is the union operator. See that we have a set of sets.
• 04-03-2008
inevitable
This uses a different recursive strategy. I need one that refers to it's previous set size rather than the previous n.
• 04-03-2008
m37h0d
Quote:

Originally Posted by inevitable
This uses a different recursive strategy. I need one that refers to it's previous set size rather than the previous n.

not sure if it's exactly what you're looking for here, but to compute all possible combinations of X length words of values [1,Y-1], count from 0->(X^Y) in base y.

here's something i c&p'd out of an old PHP project.

Code:

```\$test_base = 9; \$steps_x = 5; \$steps_y = pow(\$test_base,\$steps_x); for(\$i=0;\$i<\$steps_y;\$i++) {         \$row = base_convert(\$i,10,\$test_base);         print(\$row); }```