Grokking 235

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int total = Arrays.stream(stones).sum();
        boolean[][] dp = new boolean[n + 1][total + 1];

        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        // Find all sums we can make from inputs
        for (int i = 1; i <= n; i++) {
            for (int sum = 1; sum <= total; sum++) {
                dp[i][sum] = dp[i - 1][sum];
                if (stones[i - 1] <= sum) {
                    dp[i][sum] |= dp[i - 1][sum - stones[i - 1]];
                }
            }
        }

        /*
          Find the minimum difference between 2 sums
          Diff = leftSum - rightSum
          Total = leftSum + rightSum
                = leftSum + leftSum - Diff

          => Diff = |Total - 2 * leftSum|
        */
        int leftSum = 0;
        for (int sum = 0; sum <= total / 2; sum++) {
            if (dp[n][sum]) {
                leftSum = sum;
            }
        }

        return Math.abs(total - 2 * leftSum);
    }
}