尝试将一个 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

在克隆 ArrayList 之前，您要将原始列表 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));

注意：由于你的早真return，并不是所有的无效案例都被访问

编辑：更多解释

假设你执行了你的方法（来自问题）。这不会访问所有可能的组合并提供错误的结果。

之所以没有检查所有组合，是因为您在制作副本之前将元素从 b 转移到 a。

让我们看看 for 循环中发生了什么：

for循环进入i == 0
元素从（原始）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]

并且该方法的结果是 'true'，因为拆分为 [1,4] 和 [2,3] 得到相同的平均值。
没有更多的输出，因为当b的size为1时，那么只returned 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]

Answer 2

如果你想打印 a 的所有不可能的值，你不能从 for 循环 return，你将在第一个正组合时跳出它。

这对我有用（抱歉用 C# 重写了它，因为我没有 java IDE 可用的 atm，但我认为你掌握了这些变化）：

private bool CanSplitArraySameAverage(List<int> a, List<int> b)
    {
        
        double aSum = 0, bSum = 0;

        foreach (var it in a)
        {
            aSum = aSum + it;
        }

        foreach (int it in b)
        {
            bSum = bSum + it;
        }

        if ((a.Any() && b.Any()) && (bSum / b.Count() == aSum / a.Count()))
        {
            return true;
        }

        bool canSplit = false;
        if(b.Count() != 1)
        {
            for (int i = 0; i < b.Count(); i++)
            {
                List<int> newA = new List<int>(a);
                List<int> newB = new List<int>(b);

                newA.Add(newB.ElementAt(i));  
                newB.RemoveAt(i);

                if (this.CanSplitArraySameAverage(newA, newB))
                {
                    canSplit = true;
                }

            }
        }

        if (!canSplit)
        {
            Console.WriteLine("Return :" + String.Join("-", a));
        }
        return canSplit;  
    }

给出输出：

Return :1-2-3
Return :1-2-4
Return :1-2
Return :1-3-2
Return :1-3-4
Return :1-3
Return :2-1-3
Return :2-1-4
Return :2-1
Return :2-4-1
Return :2-4-3
Return :2-4
Return :3-1-2
Return :3-1-4
Return :3-1
Return :3-4-1
Return :3-4-2
Return :3-4
Return :4-2-1
Return :4-2-3
Return :4-2
Return :4-3-1
Return :4-3-2
Return :4-3

没有 2-3 或 1-4 的组合

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

Trying to split an int array into 2 and check if their averages can be equal using a recursive approach

java

recursion

arraylist

dynamic-programming