Question

用递归 求出一个string的所有子集 java

cat ==== cat, ca, ct, at, c, a, t, 还有个空集
public ArrayList<String> getSubsets()
{
ArrayList<String> subsets = new ArrayList<String>();
if(word.length() == 0)
{
subsets.add(word);
return subsets;
}

for(int i = 0; i < word.length(); i++)
{
String firstWord = word.substring(0, 1);
String remainWord = word.substring(1);

subsets.add(firstWord);

SubsetGenerator remainSubsetGenerator = new SubsetGenerator(remainWord);
ArrayList<String> remainWordSubsets = remainSubsetGenerator.getSubsets();

for(String s : remainWordSubsets)
{
subsets.add(firstWord + s);
}
}
return subsets;
}

这是我现在写的得出[r, r, r, ru, ru, ru, ru, ru, ru, rum, rum, rum, rum, rum, rum, rum, rum, rum, rum, rum, rum]
Expected: [, m, r, rm, ru, rum, u, um]

Answer 1

其实问题还是比较明显的，比如subsets.add(firstWord);这句话在for循环中重复执行，但是显然firstWord每次都是word.substring(0, 1);而在整个for循环中，你又没有对word重新赋值过。这也就是为什么你的输出有那么多相同的字符串吧

另外，理论上你每次新建一个SubsetGenerator，就不能算递归了

public static ArrayList<String> getSubSequences(String word) {
ArrayList<String> list = new ArrayList<String>();
doGetSubSequences(word, "", list);
return list;
}

private static void doGetSubSequences(String word, String s,
ArrayList<String> list) {
if (word.length() == 0) {
list.add(s);
return;
}

String tail = word.substring(1);
doGetSubSequences(tail, s, list);
doGetSubSequences(tail, s + word.charAt(0), list);
}