2
\$\begingroup\$

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?

\$\endgroup\$
2
  • \$\begingroup\$ 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.) \$\endgroup\$
    – greybeard
    Dec 24, 2021 at 15:28
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – greybeard
    Dec 24, 2021 at 16:11

1 Answer 1

2
\$\begingroup\$

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;

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.