java - 了解计算幂集时的递归流程

Question

我找到了一个计算数组幂集的代码。

我无法理解 subseq() 方法内部发生了什么。根据我的理解和我在调试时看到的内容 -

1. first [] is added.
2. Goes inside loop , `i=0` adds `[1]`
3. recursive call , `i=1` adds `[1,2]`
4. recursive call , `i=2` adds `[1,2,3]`

当i =3时，它不应该进入循环本身，怎么在这之后，执行就要remove了。你能帮我理解这一点吗？

public class printSubSequences {

    public static void main(String[] args) {
        int[] num = {1,2,3};
        List<List<Integer>> subsets = new ArrayList<>();
        subseq(0, num, new ArrayList<Integer>(), subsets );

        System.out.println(subsets);

    }

    public static void subseq(int index, int[] num, List<Integer> current, List<List<Integer>> subsets) {

        subsets.add(new ArrayList<>(current));
        for(int i = index ; i< num.length; i++) {
            current.add(num[i]);
            subseq(i+1, num, current, subsets);
            current.remove(current.size() -1);
        }

    }

}

Answer 1

很简单backtracking算法。

当递归触底时:

subseq(0, {1,2,3}, [], []);
    subseq(1, {1,2,3}, [1], [[]]);
        subseq(2, {1,2,3}, [1,2], [[], [1]]);
            subseq(3, {1,2,3}, [1,2,3], [[], [1], [1,2]]); <---

在此帧中跳过for循环，因为i == num.length；因此，代码返回到前一帧，其中 i 为 2，并且紧接着 subseq(...) 之后的行正在被替换执行:

current.remove(current.size() -1);

此时current = [1,2,3]，因此最后一个元素3将被删除。