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

问：

我正在尝试使用回溯/递归找到 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]）将在哪里找到子集？

Java 子集回溯

行为差异的主要原因在于 Java 处理对象和引用的方式。当您传递给递归函数并使用修改它时，您正在更改其他递归调用使用的同一对象。Java 按值传递对象引用，导致不良行为和错误结果，因为一次调用中的修改会影响其他调用。在初次非工作尝试中：tt.add(s[i]);ArrayList

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”的同一对象。接下来发生的情况是，任何后续递归调用和调用调用堆栈的任何函数都引用了此对象，也将感知到此修改。因此，这会导致生成不正确的子集。t.add(s[i]);ArrayListArrayList

在第二次成功尝试中：

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

0赞 Roshin Raphel 9/25/2023 #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 是非零的，但是当您以递归方式再次调用该函数时，对于原型，，再次变为 null，因此条件失败。所以没有更新。findSubsets(s,tmp1,i+1,result)findSubsets(char[] s,ArrayList<Character> t,int i,ArrayList<ArrayList<Character>> result)tif(t.size()>0)result

上一个：通过 chrome 扩展保存 POST REQUEST 的 REQUEST body（payload）

下一个：从文件中读取文本时接收数值和字母

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

finding subsets of a Array in java using backtracking/recursion

评论