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.

Keldah

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)).

Hart

While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review – Awhirl

@manetsus - The text of the answer gives the essential point, which is the name of the problem the OP is trying to answer. The link, in this case, is not necessary to answer the question; it's just icing on the cake. – Hart

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

Pileup