递归生成子集的问题

Question

因此，该算法通过使用参数i来引用Ai来生成集合A的子集，在每个步骤中，有两个调用，一个包含Ai，另一个不包含Ai。当为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

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