破解编码面试：为什么递归子集算法增加而不是减少索引？

Question

在第 6 版 Cracking the Coding Interview 的第 8 章中，有一个找到所有子集的问题，这是给定的解决方案：

Arraylist<Arraylist<Integer>> getSubsets(Arraylist<Integer> set, int index) {
    Arraylist<Arraylist<Integer>> allsubsets;
    if (set.size()== index) {//Base case - add empty set
        allsubsets = new Arraylist<Arraylist<Integer>>(); 
        allsubsets.add(new Arraylist<Integer>()); // Empty set
    } else {
        allsubsets = getSubsets(set, index+ 1);
        int item = set.get(index);

        Arraylist<Arraylist<Integer>> moresubsets = new Arraylist<Arraylist<Integer>>();

        for (Arraylist<Integer> subset : allsubsets) {
            Arraylist<Integer> newsubset = new Arraylist<Integer>();
            newsubset.addAll(subset);
            newsubset.add(item);
            moresubsets.add(newsubset);
        }
        allsubsets.addAll(moresubsets);
    }
    return allsubsets;
}

据我了解，我需要将当前元素添加到为给定集合中的前一个元素找到的所有子集中。我不明白为什么递归调用将 index+1 作为给定参数而不是 index-1。这是错字还是我的理解不正确？

Answer 1

这个递归函数背后的想法似乎是 getSubsets(set, i) 意味着 "generate and return all subsets of the elements in the input list s from index i and forward." 如果你看一下递归是如何工作的，它是这样的：

如果 i == set.size()，那么我们应该从索引 set.size() 开始生成元素的所有子集。这里没有任何元素，所以唯一的子集是空集。
否则，请注意 set 的每个元素子集，从索引 i 开始，要么包含第 i 个元素，要么不包含。不包含第 i 个元素的子集恰好是 set 从位置 i + 1 开始并向前的子集。这样做的是通过获取这些子集，然后将第 i 个元素添加到它们而形成的。

所以从这个意义上说，递归转到索引 i + 1 而不是 i - 1 的原因是因为直觉是查看从位置 i 开始并继续的元素子集到最后。

您也可以编写此函数以列出从索引 0 向上到索引 i 的子集，如果您愿意，然后将 i 向下移至 0。这是执行此操作的完全合理的方法以及自己编写代码的好练习！

破解编码面试：为什么递归子集算法增加而不是减少索引？

Cracking the Coding Interview: Why does the recursive subset algorithm increase the index rather than decreasing it?

java

algorithm

recursion

powerset