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.

Thanks for your help!

What's your best attempt?

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

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.

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.

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

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);
}

---