java - 破解编码面试 : Why does the recursive subset algorithm increase the index rather than decreasing it?

Question

在 Cracking the Coding Interview, 6th Edition 的第 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) 意味着“生成并返回输入列表 s 中元素的所有子集来自索引 i 并转发。”如果您查看递归的工作原理，它的工作原理如下:

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

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

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