Rigid recursive task

Question

I struggled with a question that I am trying to solve in preparation for testing, and I thought I could use your help. I need to write a Boolean method that takes an array of integers (positive and negative), and returns true, if the array can be divided into two groups equally , the number of all group numbers are equal to each group. For exmaple for this array:

int[]arr = {-3, 5, 12, 14, -9, 13};

The method will return true since -3 + 5 + 14 = 12 + -9 + 13.

For this array:

int[]arr = {-3, 5, -12, 14, -9, 13};

The method will return false, because even if -3 + 5 + 14 + -12 = -9 + 13, the number of numbers in each part of the equation is not equal.

For an array:

int[]arr = {-3, 5, -12, 14, -9};

The method will return false since the length of the array is not defined.

, , , .

, , , , .

- -, .

!

Answer 1

, Java.

, , . . :

class Balance {
  public static void main(String[] args) {
    System.out.println(balanced(-3, 5, 12, 14, -9, 13));   // true
    System.out.println(balanced(-3, 5, -12, 14, -9, 13));  // false
  }

  private static boolean balanced(int... nums) {
    // First check if there are an even number of nums.
    return nums.length % 2 == 0
        // Now start the recursion:
        && balanced(
            0, 0,  // Zero numbers on the left, summing to zero.
            0, 0,  // Zero numbers on the right, summing to zero.
            nums);
  }

  private static boolean balanced(
      int leftCount, int leftSum,
      int rightCount, int rightSum,
      int[] nums) {
    int idx = leftCount + rightCount;
    if (idx == nums.length) {
      // We have attributed all numbers to either side of the equation.
      // Now check if there are an equal number and equal sum on the two sides.
      return leftCount == rightCount && leftSum == rightSum;
    } else {
      // We still have numbers to allocate to one side or the other.
      return
          // What if I were to place nums[idx] on the left of the equation?
          balanced(
              leftCount + 1, leftSum + nums[idx],
              rightCount, rightSum,
              nums)
          // What if I were to place nums[idx] on the right of the equation?
          || balanced(
              leftCount, leftSum,
              rightCount + 1, rightSum + nums[idx],
              nums);
    }
  }
}

. O (2 ^ n), , , n, , .

Answer 2

Partition. , , , ( , , ). , , , . n , n/2 ( ) .

Sum Target := Sum / 2, .

f(arr,a,count) := true
                  if there is a subset of arr summing up to a with
                  exactly count elements
                  false
                  otherwise

f(arr,a,count) = (arr[0] == a && count == 1)
                 ||
                 (a == 0 && count == 0)
                 if arr contains only one element
                 f(arr\arr[0], a, count)
                 ||
                 f(arr\arr[0], a - arr[0], count -1)
                 if arr contains more than one element

|| , && , \ . arr . , a ; , , 0 , .

, f(arr,Target,n/2) .

Answer 3

, . , .

, , : , , , , .

, . :

• : , , , , , , .
• , , , , .

, , , , , 2 , .

, :

public boolean isValidSet(MySet<int> inputSet, int sizeDifferenceSet1minus2)
{
    if (inputSet.isEmpty())
    {
         return sizeDifferenceSet1minus2== 0;
    }

    int first = inptuSet.takeFirst();
    return isValidSet(inputSet.copyMinusFirst(), sizeDifferenceSet1minus2+ first)
              || isValidSet(inputSet.copyMinusFirst(), sizeDifferenceSet1minus2+ -1 * first);
}

, .

, , , , . , , , , , , , . , , 1 2, ( ).

, !

For some background information: This problem is called the Partition Problem , which is famous for being NP-complete (which means that it probably cannot be solved efficiently for large volumes of input data, but it’s very easy to verify that the partition is really a solution .