Divide optimally an array into two subarrays so that sum of elements in both are same

Question

I'm given the equation like this one:

    n = 7
    1 + 1 - 4 - 4 - 4 - 2 - 2

How can I optimally replace operators, so that the sum of the equation is equal to zero, or print  -1. I think of one algorithm, but it is not optimal. I have an idea to bruteforce all cases with complexity O(n*2^n), but (n < 300).

Here is the link of the problem: http://codeforces.com/gym/100989/problem/M.

Answer 1

You are trying to solve the Partition Problem; i.e. partition your integers into two subsets, whose sums are the same, and assign positive sign to integers in one subset and negative signs to those in the other subset.

In your particular problem you have a low limit on both the number of integers and the value of those integers. You can apply a standard dynamic algorithm approach with the inclusion/exclusion approach; i.e. finding a subset of the first n integers that sums to i, by considering the case where the last of those integers is not used (so you need a subset of the first n-1 integers summing to i) and where it is used (a subset of the first n-1 integers summing to i - val(n)).

Answer 2

Here is an idea:

1. Sort the 2nd to Nth elements descending (the problem stays the same).
2. Build the cumulative sum in reverse. [1 4 3 2] => [10 9 5 2] to get an upper bound for the highest number you can still reach with the remaining integers.
3. Use the bounds from the reverse cumulative sum to prune.

In Java:

// assuming the numbers are positive
// (ignore operator when parsing, line.split("[ +-]+") will do)
public static int canReach0(int[] numbers) {
  sort(numbers, 1); // sort(array, offset) doesn't matter what algorithm
                    // for 300 elements and compared to the complexity of the rest
  int[] revSum = new int[numbers.length];
  revSum[numbers.length - 1] = numbers[numbers.length - 1];
  for (int i = numbers.length - 2; i >= 0; i--)
    revSum[i] = revSum[i + 1] + numbers[i];
  int sum = numbers[0];
  if (sum == revSum[1])
    return 0;
  return solve(numbers, 1, sum, revSum);
}

private static int solve(int[] numbers, int index, int sum, int[] revSum) {
  if (index == numbers.length - 1)
    return -1;
  int high = sum + numbers[index];
  if (high == revSum[index + 1] || 
      (high < revSum[index + 1] && solve(numbers, index + 1, high, revSum) == 0))
    return 0;
  int low = sum - numbers[index];
  if (low == -revSum[index + 1] ||
      (low > -revSum[index + 1] && solve(numbers, index + 1, low, revSum) == 0))
    return 0;
  return -1;
}