1049. Last Stone Weight II

Problem Statement

[Last Stone Weight II - LeetCode](https://leetcode.com/problems/last-stone-weight-ii/ Aditya Verma : Minimum Subset Difference

Pattern: Pattern DP Subset Sum Related: 416. Partition Equal Subset Sum

---

Solution

This is a minimise subset/partition sum

Integer[][] dp;  
  
int f(int[] nums, int n, int k) {  
   if (n < 0) return 0;  
   if (dp[n][k] != null) return dp[n][k];  
   if (nums[n] <= k) return dp[n][k] = Math.max(  
         nums[n] + f(nums, n - 1, k - nums[n]),  
         f(nums, n - 1, k)  
      );  
   return dp[n][k] = f(nums, n - 1, k);  
}  
  
public int lastStoneWeightII(int[] stones) {  
   int sum = 0 ;  
   for (int num : stones) sum += num;  
   dp = new Integer[stones.length + 1][sum / 2 + 1];  
   int maxPartitionSum = f(stones, stones.length - 1, sum / 2); // find partition w sum <= sum/2  
   return (sum - maxPartitionSum) - maxPartitionSum;   // sum of (second partition - first partition)  
}

TC : $n\ast sum/2$ - 4ms 85% solution SC :

Notes

Logic

For any sequence of operations, the algebra boils down to difference of two sums

For example

(((a - b) - c) - d) = a - b - c - d = (a) - (b + c + d)  
((d - (a - b) )- c) = d - a + b - c = (d + b) - (a + c)

So all we have to do is find the one of the groups, such that its sum is as close as possible to the other, so if total sum is 24, we have to find the group with sum closest to 12.

Essentially it boils down to an Pattern DP Subset Sum problem.

Iterative

todoleetcode