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

Before cloning the ArrayLists, you are adding the value from the original List b to the original List a.

This means when doing the first call of your recursive method, the first element of the original List b (in your case: 1) will always be the first element of newA.

The solution to this is to transfer the element after doing the copy:

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

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

Note: Due to your early true return, not all invalid cases are visited

Edit: More explanation

Assuming you make execute your method (from the question). This will not visit all possible combinations and deliver a wrong result.

The reason, why not all combinations are examined is, because you are transfering elements from b to a before making a copy.

Lets take a look at what happens in the for-loop:

• The for loop is entered with i == 0
• element is transfered from (original) b to a
• now a = [1], b = [2,3,4]
• the recursion part happens
• i is increased. now i == 1
• because you removed the first element from the original b, the next element that will be added is 3 (because i == 1)
• this leads to that, that in a further step the combination of [1,4] [2,3] is never examined, and your method delivers a wrong result.

Here is the fixed code of your method:

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
}

When executing this method with two lists a and b, where a is empty and b contains [1,2,3,4], the output is:

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

and the result of the method is 'true', because splitting into [1,4] and [2,3] delivers the same average.
There is not more output, because when the size of b is 1, then only false is returned, without making an output.

The combinations checked in the different recursion levels are:

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]

If you want to print all the not possible values of a you can't return from the for-loop, the you will break out of it on the first positive combination.

This works for me (sorry rewrote it in C# since I don't have java IDE available atm but I think you grasp the changes):

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;  
    }

Gives the output:

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

No combinations of 2-3 or 1-4