1. ## 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.

What do you think you should recurse on? What should be your stopping point?

3. 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.

4. 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.

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

6. 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);
}```