java - 尝试将 int 数组拆分为 2 并使用递归方法检查它们的平均值是否相等

Question

我的代码

    public boolean canSplitArraySameAverage(ArrayList<Integer> a, ArrayList<Integer> b) {

        double aSum = 0, bSum = 0;

        for (int it : a)   // aSum
            aSum = aSum + it;


        for (int it : b)   // bSum
            bSum = bSum + it;


        if ((!a.isEmpty() && !b.isEmpty()) && (bSum / b.size() == aSum / a.size())) //  Equal Average Possible
            return true;


        if (b.size() == 1)  //  Solution not possible, returning on reaching base case
            return false;


        for (int i = 0; i < b.size(); i++) { 

            a.add(b.remove(i));  // Transferring element from b to a

            // Creating Deep Copies
            ArrayList<Integer> newA = (ArrayList<Integer>) a.clone();
            ArrayList<Integer> newB = (ArrayList<Integer>) b.clone();

            if (canSplitArraySameAverage(newA, newB))
                return true;  // Early true return

        }

        System.out.println("Return :" + a);  
        return false;  //  Solution not possible, returning after exhausting for loop
    }

Logical Flow on how the code should execute
传递值 a[] 和 b[1 2 3 4]
当达到负基本情况(b[] size = 1)时，我希望 a[] 的值如下

[1 2 3]
[1 2 4]
[1 2]
[1 3 2]
[1 3 4]
[1 3]
and so on

但是我的代码执行为

[1 2 3]
[1 2 4]
[1 3 2]
[1 3]
and terminates

我不确定问题出在哪里，我怀疑它与 return 语句有关。

Answer 1

在克隆 ArrayLists 之前，您要添加来自原始列表的值 b到原始列表 a .
这意味着在第一次调用递归方法时，原始列表的第一个元素 b (在您的情况下:1)将始终是 newA 的第一个元素.
解决这个问题的方法是在复制后转移元素:

      // Creating Deep Copies
      ArrayList<Integer> newA = (ArrayList<Integer>) a.clone();
      ArrayList<Integer> newB = (ArrayList<Integer>) b.clone();

      newA.add(newB.remove(i));

注意:由于您的早期真实返回，并非所有无效案例都被访问

编辑:更多解释
假设您执行您的方法(来自问题)。这不会访问所有可能的组合并提供错误的结果。
之所以不检查所有组合，是因为您正在从 b 传输元素。至 a在制作副本之前。
让我们看看在 for 循环中发生了什么:

使用 i == 0 进入 for 循环

元素是从(原始)转移的b至 a

现在 a = [1], b = [2,3,4]

递归部分发生

我增加了。现在 i == 1

因为您从原始 b 中删除了第一个元素, 下一个要添加的元素是 3 (因为 i == 1 )

这导致，在进一步的步骤中， [1,4] [2,3] 的组合永远不会被检查，并且您的方法会提供错误的结果。

这是您的方法的固定代码:

public static boolean canSplitArraySameAverage(ArrayList<Integer> a, ArrayList<Integer> b) {

  double aSum = a.stream().reduce(0, (x,y) -> x+y);
  double bSum = b.stream().reduce(0, (x,y) -> x+y);
  
  if ((!a.isEmpty() && !b.isEmpty()) && (bSum / b.size() == aSum / a.size())) //  Equal Average Possible
    return true;
  
  if (b.size() == 1) //  Solution not possible, returning on reaching base case
    return false;
  
  for (int i = 0; i < b.size(); i++) {
    // Creating Deep Copies
    ArrayList<Integer> newA = (ArrayList<Integer>) a.clone();
    ArrayList<Integer> newB = (ArrayList<Integer>) b.clone();
  
    // Transferring element from newB to newA
    newA.add(newB.remove(i));
  
    if (canSplitArraySameAverage(newA, newB))
      return true;  // Early true retur
  }
  
  System.out.println("Return :" + a);
  return false;  //  Solution not possible, returning after exhausting for loop
}

使用两个列表执行此方法时 a和 b ，其中 a 为空且 b包含 [1,2,3,4] ，输出为:

Return :[1, 2]
Return :[1, 3]

并且该方法的结果是“真”，因为拆分为 [1,4] 和 [2,3] 提供相同的平均值。
没有更多的输出，因为当 b 的大小为1，则只返回false，不进行输出。
在不同递归级别检查的组合是:

Recursion-Level: 0; a = [], b = [1, 2, 3, 4]
Recursion-Level: 1; a = [1], b = [2, 3, 4]
Recursion-Level: 2; a = [1, 2], b = [3, 4]
Recursion-Level: 3; a = [1, 2, 3], b = [4]
Recursion-Level: 3; a = [1, 2, 4], b = [3]
Recursion-Level: 2; a = [1, 3], b = [2, 4]
Recursion-Level: 3; a = [1, 3, 2], b = [4]
Recursion-Level: 3; a = [1, 3, 4], b = [2]
Recursion-Level: 2; a = [1, 4], b = [2, 3]