Given an array return true if can be splitted to two groups with same number of cells and same sum

Question

Given an array, the method should return true if you can split it to two groups with the same number of cells and so the sum will be equal. It needs to be done by recursion, and can't change the array values/order, recursive private methods are allowed.

Examples on random arrays:

//{-3,5,12,14,-9,13} returns true
//{-3,5,-12,14,-9,13}; returns false,can find the sum but the groups are of 4 cells and 2 cells
//{-3,5,-12,14,-9}; returns false,cant split the array to two groups

Method name:

public static boolean equalSplit(int [] arr)

This is what I did:

 public static boolean equalSplit(int [] a)
 {
 return equalSplit(a,0,0,0,0,0);
 
 }
 
 
 private static boolean equalSplit(int [] a , int sum1 , int sum2 , int i,int c1,int c2)
 {
 
 if( i == a.length)
 
 return(sum1 == sum2 && c1 == c2);
 
 
 return
 equalSplit(a,sum1+a[i],sum2,i+1,c1 +1,c2) ||
 equalSplit(a,sum1,sum2+a[i] ,i+1,c1 ,c2+1);
 
 }

Do you see any problems here?

• greybeard: can't change the array values/order I'm tempted to add for larger arrays, additional storage shall be small in comparison. (Your guess why I'd rather not be caught doing so.)
• greybeard: Welcome to Code Review@SE. any problems here? You treat sum1/2, c1/2, base case as if they were independent. They are not, there are many futile operations.

Answer 1

Trivial Rejects

You are missing some easy checks which can rapidly yield a false result. First, if a.length is not even, you cannot divide the array into two evenly sized groups. Second, if \$\sum a_i\$ is not even, again you cannot divide the array into two groups which sum to the same value.

Redundancy

If including a[0] in sum1 can't find a solution, trying it in sum2 is also guaranteed to fail, doubling the time required to produce the false result.

Pruning

For c1 == c2, neither can be larger than a.length/2. You can return false without ever exploring deeper in those subtrees.

Code Formatting

Your spacing is inconsistent. Eg) int [] a , int sum1 , int sum2 , int i,int c1,int c2 Use one space after commas, no spaces before them.

Indentation is inconsistent.

Use of blank lines is inconsistent.

There is no need for parentheses in your return statements. return(expr); should be return expr;