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

标签 java algorithm recursion powerset

在 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 .这是打字错误还是我的理解不正确?

最佳答案

这个特定递归函数背后的想法似乎是 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。这是一个完全合理的方法,也是一个很好的练习,可以自己编写代码!

    关于java - 破解编码面试 : Why does the recursive subset algorithm increase the index rather than decreasing it?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41685905/

    相关文章:

    java - 打开弹出窗口时程序闪烁

    python - turtle 的螺旋功能-如何使其停止?

    javascript - 递归 Object.defineProperty() getter

    c++ - lambda 如何捕获自身以进行异步调用?

    java - 非静态时的变量初始化问题

    java - javadoc中的字符串内容

    arrays - 4个元素数组中的两个最大数字

    algorithm - 为什么加权快速联合算法会考虑树的大小而不是树的高度?

    c - 如何在c中的一个char数组的中间插入多个char?

    java - 在Apache Ignite中获取内存指标