leetcode - knapsack dp - 1049. Last Stone Weight II

1049. Last Stone Weight II (weekly 137)

1. Given an integer (stone) array, separate the integers into two sets, named A, B
2. return the minimum value of Sum(A) - Sum(B)

Note:

1. 1 <= stones.length <= 30
2. 1 <= stones[i] <= 100

Reference from committed code.

Very smart.

int lastStoneWeightII(vector<int>& stones) {
  constexpr int MAX = 3000 / 2 + 100 + 1;
  bitset<MAX> possibleSum;
  possibleSum[0] = true;

  for (int s : stones)
    possibleSum = possibleSum | (possibleSum << s);

  int total = accumulate(stones.begin(), stones.end(), 0);

  // find left partition.
  int leftPart = 0;
  for (int i = total / 2; i >= 0; --i)
    if (possibleSum[i]) {
      leftPart = i;
      break;
    }

  // find right partition.
  int rightPart = 0;
  for (int i = (total + 1) / 2; i <= total; ++i)
    if (possibleSum[i]) {
      rightPart = i;
      break;
    }

  return rightPart - leftPart;
}

by neal_wu's contest solution.

int lastStoneWeightII(vector<int>& stones) {
    int n = stones.size();
    vector<bool> possible(2 * MAX + 1, false);
    possible[MAX] = true;

    for (int stone : stones) {
        vector<bool> next_possible(2 * MAX + 1, false);

        for (int x = 0; x <= 2 * MAX; x++)
            if (possible[x])
                next_possible[x + stone] = next_possible[x - stone] = true;

        possible = next_possible;
    }

    for (int i = 0; i <= MAX; i++)
        if (possible[MAX + i])
            return i;

    return -1;
}