在java中使用回溯/递归查找数组的子集

Question

我正在尝试使用回溯/递归查找 ArrayList 的所有子集，下面是我查找子集的主要方法和方法

    public static void main(String[] args) {
        char[] s = {'a','b','c','d','e'};
        ArrayList<ArrayList<Character>> result= new ArrayList<ArrayList<Character>>();
        ArrayList<Character> t= new ArrayList<Character>();
        findSubsets(s,t,0,result);
    }
    static void findSubsets(char[] s,ArrayList<Character> t,int i,ArrayList<ArrayList<Character>> result) {
        if(i >= s.length) {
            if(t.size()>0) {
                result.add(t);
                printArrayListOfArrayList(result);
            }
            return;
        }
        findSubsets(s,t,i+1,result);
        ArrayList<Character> tmp1 = new ArrayList<>(t);  
        tmp1.add(s[i]); 
        findSubsets(s,tmp1,i+1,result);
    }

我之前尝试过

        findSubsets(s,t,i+1,result);
        t.add(s[i]); 
        findSubsets(s,tmp1,i+1,result);

它没有工作，下面的代码工作完美

        findSubsets(s,t,i+1,result);
        ArrayList<Character> tmp1 = new ArrayList<>(t);  
        tmp1.add(s[i]); 
        findSubsets(s,tmp1,i+1,result);

为什么 t.add(s[i]) 然后调用递归函数找不到子集？ 添加了相同数据的新列表 tmp1.add(s[i]) 在哪里会找到子集？

Answer 1

行为差异的主要原因在于Java如何处理对象和引用。当您将

t

传递给递归函数并使用

t.add(s[i]);

修改它时，您正在更改其他递归调用使用的相同

ArrayList

对象。 Java 按值传递对象引用，导致不期望的行为和不正确的结果，因为一个调用中的修改会影响其他调用。在您最初的非工作尝试中：

findSubsets(s,t,i+1,result);  // Recursive call with original t
t.add(s[i]);  // Modifying t
findSubsets(s,t,i+1,result);  // Recursive call with modified t

在此代码片段中，当您调用

t.add(s[i]);

方法时，您实际上是在更改名为“t”的同一个

ArrayList

对象。接下来发生的事情是，任何后续的递归调用和任何调用具有此

ArrayList

对象引用的调用堆栈的函数也将感知到此修改。结果，这导致生成不正确的子集。

在您成功的第二次尝试中：

findSubsets(s,t,i+1,result);  // Recursive call with the original t
ArrayList<Character> tmp1 = new ArrayList<>(t);  // Creating a new ArrayList object with the same content as t
tmp1.add(s[i]);  // Modifying tmp1
findSubsets(s,tmp1,i+1,result);  // Recursive call with tmp1

Answer 2

我希望你尝试过：

        findSubsets(s,t,i+1,result);
        ArrayList<Character> tmp1 = new ArrayList<>(t); 
        t.add(s[i]); 
        findSubsets(s,tmp1,i+1,result);

而不是：

        findSubsets(s,t,i+1,result);
        t.add(s[i]); 
        findSubsets(s,tmp1,i+1,result);

在这种情况下，t不为零，但是当您再次调用该函数时，

findSubsets(s,tmp1,i+1,result);

，对于原型

findSubsets(char[] s,ArrayList<Character> t,int i,ArrayList<ArrayList<Character>> result)

，

t

再次变为空，因此条件

if(t.size()>0) 

失败。