java - 递归生成子集的问题

Question

因此，该算法通过使用参数i来引用A[i]来生成集合A的子集，在每一步中，有两次调用，一次包括A[i]，一次不包括A[i]。当 i==n 时搜索停止。

所以，这是有道理的，但我无法理解这里最后一条语句的作用..

void search(int i, ArrayList<Integer> subset,ArrayList<Integer> A, int n){
        if (i==n) System.out.println(subset);
        else{
            search(i+1,subset,A,n);
            subset.add(A.get(i));
            search(i+1,subset,A,n);
            subset.remove(subset.size()-1); /*Why do we need to do this? I am not making any function call after this*/
        }
}

我尝试排除最后一条语句，但随后它重复了子集中的元素。最后一条语句有什么用？

Answer 1

您拥有在所有递归级别共享的唯一 subset 实例。

因此，在使用 item 之后，您应该以 subset 的相同状态返回到较低级别。

想象一下调用树

[]
     []
     [2]  *

[1]  
     [1]
     [1 2]

生成子集[2](代码点*)后，您返回到第一级并且必须生成子集[1]。但是 subset 对象已经包含项目 2，所以如果不删除 *

中的项目 2 就不可能生成 [1]

---

如果实现创建了参数的新副本，则不需要恢复状态。