power set recursion
Hi, I wish someone can help. Im really bad in recursion.
I am supposed to solve this program using recursion. Input is a String, say "abcd". and Im supposed to get the output as all the possible sets of {a,b,c,d}.
the output should b:
// this is an empty line for null set.
a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d
I have been looking at it andsad to say that I have absolutely no idea of how my algorithm should goes... i can see the pattern of printing an additional 1 char each line until it is == to inputString.length(). But i just cant think of the recursion method...
Someone pls help.. Thanks.
cheers,
[748 byte] By [
appledoea] at [2007-9-30 1:07:13]
I'll just show you a simple table; just two columns -- the first shows the binary representation of
consecutive numbers , the second shows a set -- numberset
-
0000....
0001...a
0010..b.
0011..ba
0100.c..
0101.c.a
0110.cb.
0111.cba
1000d...
1001d..a
1010d.b.
1011d.ba
1100dc..
1101dc.a
1110dcb.
1111dcba
Does that ring a bell?
kind regards,
Jos
What is recursion all about? It's about base cases, and general cases that can be broken down, eventually leading to a base case.
We know the base case is for a string of size 0 or 1.
private static String[] subsets(String s)
{
if (s.length()==1)
return new String[]{s,""};
if (s.length()==0)
return new String[]{s};
//oh no! now what?
}
What's the general case? It's that we have a string of length n. So we break that up into a string of length 1, and a string of length n-1.
We pass both values back into out function, and create all combinations of the results.
//pass a substring of length 1 and...
String[] set1 = subsets(s.substring(0,1)); //size is 2
//... a substring of length n-1 into our function
String[] set2 = subsets(s.substring(1));
//create some storage to hold the return value
String[] subsets = new String[2*set2.length];
//fill in combinations from set1 (whose size is 2), and set2
for (int i = 0; i<subsets.length; i++)
{
subsets[i] = set1[i%2] + set2[i/2]; //hopefully you're familiar with integer math in java to see how this works
}
>
