Last Stone Weight II

Find minimum absolute difference between stones

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are destroyed, and If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x. At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

Example 1:

Input: stones = [2,7,4,1,8,1] Output: 1 Explanation: We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then, we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then, we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then, we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value. Example 2:

Input: stones = [31,26,33,21,40] Output: 5

Solution

We start from zero index for base condition we check when all elements are checked we return absolute difference between w1 & w2.

else we pick current Weight in w1 or in w2 whichever gives minimum we'll return that.

var lastStoneWeightII = function(stones) {

    let n= stones.length; 

    let memo = new Map();


    function recurr(index,w1,w2){
        let key=`${index}#${w1}#${w2}`

        if(index===stones.length ){
            return Math.abs(w1-w2)
        }

        if(memo.has(key)) return memo.get(key);


        const currWeight= stones[index];

        let w1pick= recurr(index+1, w1+ currWeight, w2);

        let w2pick= recurr(index+1,w1, w2+currWeight)

        const min= Math.min(w1pick,w2pick )

        memo.set(key,min);
        return min
    }

    return recurr(0,0,0)
    
};

Tabulation

This document explains the dynamic programming (DP) approach used to partition an array into two subsets such that the absolute difference between their sums is minimized.

1. How the Algorithm Works

The problem asks us to divide an array into two subsets, $S1$ and $S2$. We know that the sum of the entire array is totalSum. Therefore, the sum of the second subset is naturally derived from the first: $S2 = totalSum - S1$.

The absolute difference between the subsets is: $\vert{}S2 - S1\vert{} = \vert{}(totalSum - S1) - S1\vert{} = \vert{}totalSum - 2 \cdot S1\vert{}$.

To minimize this difference, we just need to find all possible valid sums that a subset ($S1$) can form. Then, we look for the valid $S1$ that is closest to totalSum / 2.

Code Breakdown

1. Calculate totalSum: We first find the sum of all elements in the array.
2. Create the DP Table: We create a 2D array dp of size n (number of elements) by totalSum + 1.
   • dp[i][target] is true if a subset with sum target can be formed using elements from index 0 to i. Otherwise, it's false.
3. Base Cases:
   • dp[i][0] = true: A target sum of 0 is always possible by selecting an empty subset.
   • dp[0][arr[0]] = true: Using only the first element (arr[0]), the only non-zero sum we can form is the value of arr[0] itself.
4. DP Transitions: For every other element i and target sum target, we have two choices:
   • Don't take it (notTake): The target sum was already achievable with the previous elements (dp[i-1][target]).
   • Take it (take): The target sum is achievable by adding the current element to a previously formed sum (dp[i-1][target - arr[i]]).
   • If either choice is true, then dp[i][target] becomes true.
5. Find the Minimum Difference: We check the last row of our DP table (dp[n-1]), which represents the sums achievable using all available elements. We iterate s1 from 0 to totalSum / 2 and calculate the minimum possible difference.

2. Example Walkthrough & DP Table Visualization

Let's visualize the algorithm with the following array: arr = [3, 1, 5]

• n = 3
• totalSum = 3 + 1 + 5 = 9
• The target sums we will check go from 0 to 9.

Initializing Base Cases

• Column 0 is set to true (T) because a sum of 0 is always possible.
• Row 0 (for arr[0] = 3) is set to true at target = 3.

Filling the DP Table

Step 1: Processing i = 1 (Current element: 1)

• We look at the previous row (i=0).
• We can carry over the existing true values (sum 0 and sum 3).
• We can also add our current element (1) to those existing sums to create sum 1 (0+1) and sum 4 (3+1).

Step 2: Processing i = 2 (Current element: 5)

• We look at the previous row (i=1), where sums 0, 1, 3, 4 are true.
• We carry those over.
• We also add 5 to those existing sums to create sums 5 (0+5), 6 (1+5), 8 (3+5), and 9 (4+5).

The Final DP Table

Here is the state of the DP table after all iterations (T = true, F = false):

Calculating the Result

The algorithm now looks at the last row (i = 2). We only need to check possible sums (s1) up to totalSum / 2, which is 9 / 2 = 4.5. So, we check s1 for 0, 1, 2, 3, 4.

Looking at the last row for columns 0 to 4:

• s1 = 0: valid (T). Difference = |9 - 2(0)| = 9
• s1 = 1: valid (T). Difference = |9 - 2(1)| = 7
• s1 = 2: invalid (F). Skip.
• s1 = 3: valid (T). Difference = |9 - 2(3)| = 3
• s1 = 4: valid (T). Difference = |9 - 2(4)| = 1

The minimum absolute difference is 1, achieved by partitioning the array into subset $S1 = {3, 1}$ (sum = 4) and subset $S2 = {5}$ (sum = 5).

function minSubsetSumDifference(arr) {

  const n = arr.length;

  let totalSum = 0;

  for (let i = 0; i < n; i++) {

    totalSum += arr[i];

  }



  // Create a 2D DP table (n x totalSum + 1)

  const dp = Array.from({ length: n }, () => Array(totalSum + 1).fill(false));



  // Base case: A target sum of 0 is always possible (by picking no elements)

  for (let i = 0; i < n; i++) {

    dp[i][0] = true;

  }



  // Base case: The first element can only form a sum equal to itself

  if (arr[0] <= totalSum) {

    dp[0][arr[0]] = true;

  }



  // Fill the DP table

  for (let i = 1; i < n; i++) {

    for (let target = 1; target <= totalSum; target++) {

      // Option 1: Don't include the current element

      let notTake = dp[i - 1][target];



      // Option 2: Include the current element (if possible)

      let take = false;

      if (arr[i] <= target) {

        take = dp[i - 1][target - arr[i]];

      }



      dp[i][target] = take || notTake;

    }

  }



  // Find the minimum absolute difference by checking valid sums in the last row

  let mini = Infinity;

  for (let s1 = 0; s1 <= totalSum / 2; s1++) {

    if (dp[n - 1][s1] === true) {

      let s2 = totalSum - s1;

      let diff = Math.abs(s2 - s1);

      mini = Math.min(mini, diff);

    }

  }



  return mini;

}