递归生成子集的问题

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实例在所有递归级别共享。

因此，在使用项目后，您应该返回较低级别，具有相同的subset状态。

想象一下呼叫树

[]
     []
     [2]  *

[1]  
     [1]
     [1 2]

在创建子集[2]（代码点*）之后，返回第一级并且必须生成子集[1]。但subset对象已经包含第2项，因此如果不删除*中的第2项，则无法生成[1]

---

如果实现创建了参数的新副本，则无需还原状态。