Minimum Subset Sum Difference

🎯

Minimum Subset Sum Difference

mediumDPAmazonGoogle

Imagine you have a set of weights and want to split them into two groups so that the difference in their total weights is as small as possible. This helps in balancing loads or dividing tasks evenly.

💡 This problem is a classic example of partitioning a set into two subsets with minimum difference in sums. Beginners often struggle because it looks like a simple greedy problem but requires dynamic programming to efficiently explore all subset sums.

📋

Problem Statement

Given an array of positive integers, partition the array into two subsets such that the absolute difference between the sums of the subsets is minimized. Return this minimum difference.

1 ≤ n ≤ 1001 ≤ arr[i] ≤ 1000

💡

Example

Input"[1, 6, 11, 5]"

Output1

One optimal partition is {1, 5, 6} and {11} with sums 12 and 11, difference is 1.

• Single element array → difference equals that element
• All elements equal → difference is 0 if even count, else element value
• Array with one very large element and small others → difference close to large element
• Array with sum being odd → difference cannot be zero

🔁

Why DP?

Why greedy fails:

A greedy approach might try to put the largest element in one subset and the rest in another, but this can fail. For example, with [1, 2, 7], greedy puts 7 alone and 1,2 together, difference 4, but partitioning as {1,7} and {2} gives difference 4 as well, but other inputs show greedy fails to minimize difference.

DP state:

dp[i][w] means whether it is possible to achieve a subset sum 'w' using the first 'i' elements.

Recurrence:dp[i][w] = dp[i-1][w] OR dp[i-1][w - arr[i-1]] if w >= arr[i-1]

For each element, either we exclude it and keep the previous possibility for sum w, or include it if possible, to form sum w.

⚠️

Common Mistakes

Not handling the base case correctly in recursion

Incorrect difference calculation or infinite recursion

✅ Ensure base case returns absolute difference when all elements are processed

Using forward iteration in space-optimized DP

Overcounting elements leading to incorrect sums

✅ Iterate sums backwards to avoid reusing updated states in the same iteration

Not initializing dp[0][0] = True in tabulation

No sums considered achievable, resulting in wrong output

✅ Set dp[0][0] = True to represent sum zero achievable with zero elements

Using total_sum/2 as integer division without floor

Index errors or missing correct sums

✅ Use floor division or integer division to get correct half sum

Not clearing memo between test cases in memoization

Incorrect results due to stale cached values

✅ Clear memo dictionary/map before each new test case

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's exponential nature and why optimization is necessary.

Intuition

Try all possible subsets by deciding for each element whether to include it in the first subset or not, then compute the difference.

Algorithm

1. Start from the first element and recursively decide to include it in subset1 or not.
2. Keep track of the current sum of subset1.
3. When all elements are processed, calculate the difference between subset1 sum and total sum minus subset1 sum.
4. Return the minimum difference found among all recursive calls.

💡 The recursion explores all subsets, which is intuitive but inefficient due to repeated calculations.

Recurrence:minDiff(i, currSum) = min(minDiff(i+1, currSum + arr[i]), minDiff(i+1, currSum))

</>

Code

def min_subset_sum_diff(arr):
    total_sum = sum(arr)
    n = len(arr)
    def helper(i, curr_sum):
        if i == n:
            return abs((total_sum - curr_sum) - curr_sum)
        include = helper(i + 1, curr_sum + arr[i])
        exclude = helper(i + 1, curr_sum)
        return min(include, exclude)

# Driver code
if __name__ == '__main__':
    arr = [1, 6, 11, 5]
    print(min_subset_sum_diff(arr))  # Output: 1

Line Notes

total_sum = sum(arr)Calculate total sum once to avoid repeated summation

def helper(i, curr_sum):Recursive helper to explore subsets starting at index i

if i == n:Base case: all elements considered, compute difference

include = helper(i + 1, curr_sum + arr[i])Include current element in subset1

exclude = helper(i + 1, curr_sum)Exclude current element from subset1

return min(include, exclude)Choose the minimal difference between two choices

import java.util.*;
public class MinSubsetSumDiff {
    public static int minSubsetSumDiff(int[] arr) {
        int totalSum = 0;
        for (int num : arr) totalSum += num;
        return helper(arr, 0, 0, totalSum);
    }
    private static int helper(int[] arr, int i, int currSum, int totalSum) {
        if (i == arr.length) {
            return Math.abs((totalSum - currSum) - currSum);
        }
        int include = helper(arr, i + 1, currSum + arr[i], totalSum);
        int exclude = helper(arr, i + 1, currSum, totalSum);
        return Math.min(include, exclude);
    }
    public static void main(String[] args) {
        int[] arr = {1, 6, 11, 5};
        System.out.println(minSubsetSumDiff(arr)); // Output: 1
    }
}

Line Notes

int totalSum = 0;Initialize total sum accumulator

for (int num : arr) totalSum += num;Calculate total sum of array

if (i == arr.length)Base case: all elements processed

int include = helper(arr, i + 1, currSum + arr[i], totalSum);Include current element in subset1

int exclude = helper(arr, i + 1, currSum, totalSum);Exclude current element from subset1

return Math.min(include, exclude);Return minimal difference from both choices

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int helper(const vector<int>& arr, int i, int currSum, int totalSum) {
    if (i == arr.size()) {
        return abs((totalSum - currSum) - currSum);
    }
    int include = helper(arr, i + 1, currSum + arr[i], totalSum);
    int exclude = helper(arr, i + 1, currSum, totalSum);
    return min(include, exclude);
}

int minSubsetSumDiff(const vector<int>& arr) {
    int totalSum = 0;
    for (int num : arr) totalSum += num;
    return helper(arr, 0, 0, totalSum);
}

int main() {
    vector<int> arr = {1, 6, 11, 5};
    cout << minSubsetSumDiff(arr) << endl; // Output: 1
    return 0;
}

Line Notes

int totalSum = 0;Sum all elements once

if (i == arr.size()) {Base case: all elements considered

int include = helper(arr, i + 1, currSum + arr[i], totalSum);Include current element in subset1

int exclude = helper(arr, i + 1, currSum, totalSum);Exclude current element

return min(include, exclude);Return minimal difference

function minSubsetSumDiff(arr) {
  const totalSum = arr.reduce((a, b) => a + b, 0);
  const n = arr.length;
  function helper(i, currSum) {
    if (i === n) {
      return Math.abs((totalSum - currSum) - currSum);
    }
    const include = helper(i + 1, currSum + arr[i]);
    const exclude = helper(i + 1, currSum);
    return Math.min(include, exclude);
  }
  return helper(0, 0);
}

// Test
console.log(minSubsetSumDiff([1, 6, 11, 5])); // Output: 1

Line Notes

const totalSum = arr.reduce((a, b) => a + b, 0);Calculate total sum once

function helper(i, currSum) {Recursive helper to explore subsets

if (i === n) {Base case: all elements processed

const include = helper(i + 1, currSum + arr[i]);Include current element in subset1

const exclude = helper(i + 1, currSum);Exclude current element

return Math.min(include, exclude);Return minimal difference

⏱

Complexity

TimeO(2^n)

SpaceO(n) for recursion stack

Each element has two choices, leading to 2^n subsets explored

💡 For n=20, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's nature.

🧠

Top-Down Memoization

💡 Memoization avoids recomputing the same states by caching results, drastically improving efficiency.

Intuition

Store results of subproblems defined by index and current sum to avoid repeated calculations.

Algorithm

1. Initialize a memo dictionary keyed by (index, current sum).
2. Recursively explore including or excluding current element.
3. Before recursive calls, check if result is cached in memo.
4. Return cached result if available, else compute and store it.

💡 Memoization transforms exponential recursion into polynomial by caching.

Recurrence:minDiff(i, currSum) = min(minDiff(i+1, currSum + arr[i]), minDiff(i+1, currSum)) with memoization

</>

Code

def min_subset_sum_diff(arr):
    total_sum = sum(arr)
    n = len(arr)
    memo = {}
    def helper(i, curr_sum):
        if i == n:
            return abs((total_sum - curr_sum) - curr_sum)
        if (i, curr_sum) in memo:
            return memo[(i, curr_sum)]
        include = helper(i + 1, curr_sum + arr[i])
        exclude = helper(i + 1, curr_sum)
        memo[(i, curr_sum)] = min(include, exclude)
        return memo[(i, curr_sum)]

# Driver code
if __name__ == '__main__':
    arr = [1, 6, 11, 5]
    print(min_subset_sum_diff(arr))  # Output: 1

Line Notes

memo = {}Initialize memo dictionary to cache results

if (i, curr_sum) in memo:Check if current state already computed

memo[(i, curr_sum)] = min(include, exclude)Store computed result for reuse

return memo[(i, curr_sum)]Return cached or newly computed result

import java.util.*;
public class MinSubsetSumDiff {
    static Map<String, Integer> memo = new HashMap<>();
    public static int minSubsetSumDiff(int[] arr) {
        int totalSum = 0;
        for (int num : arr) totalSum += num;
        return helper(arr, 0, 0, totalSum);
    }
    private static int helper(int[] arr, int i, int currSum, int totalSum) {
        if (i == arr.length) {
            return Math.abs((totalSum - currSum) - currSum);
        }
        String key = i + "," + currSum;
        if (memo.containsKey(key)) return memo.get(key);
        int include = helper(arr, i + 1, currSum + arr[i], totalSum);
        int exclude = helper(arr, i + 1, currSum, totalSum);
        int res = Math.min(include, exclude);
        memo.put(key, res);
        return res;
    }
    public static void main(String[] args) {
        int[] arr = {1, 6, 11, 5};
        System.out.println(minSubsetSumDiff(arr)); // Output: 1
    }
}

Line Notes

static Map<String, Integer> memo = new HashMap<>();Memo map to cache results keyed by index and sum

String key = i + "," + currSum;Create unique key for current state

if (memo.containsKey(key)) return memo.get(key);Return cached result if available

memo.put(key, res);Store computed result for future calls

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <cmath>
using namespace std;

unordered_map<string, int> memo;

string makeKey(int i, int currSum) {
    return to_string(i) + "," + to_string(currSum);
}

int helper(const vector<int>& arr, int i, int currSum, int totalSum) {
    if (i == arr.size()) {
        return abs((totalSum - currSum) - currSum);
    }
    string key = makeKey(i, currSum);
    if (memo.find(key) != memo.end()) return memo[key];
    int include = helper(arr, i + 1, currSum + arr[i], totalSum);
    int exclude = helper(arr, i + 1, currSum, totalSum);
    memo[key] = min(include, exclude);
    return memo[key];
}

int minSubsetSumDiff(const vector<int>& arr) {
    int totalSum = 0;
    for (int num : arr) totalSum += num;
    memo.clear();
    return helper(arr, 0, 0, totalSum);
}

int main() {
    vector<int> arr = {1, 6, 11, 5};
    cout << minSubsetSumDiff(arr) << endl; // Output: 1
    return 0;
}

Line Notes

unordered_map<string, int> memo;Memo map to cache results

string key = makeKey(i, currSum);Create unique key for current state

if (memo.find(key) != memo.end()) return memo[key];Return cached result if found

memo[key] = min(include, exclude);Store computed result

function minSubsetSumDiff(arr) {
  const totalSum = arr.reduce((a, b) => a + b, 0);
  const n = arr.length;
  const memo = new Map();
  function helper(i, currSum) {
    if (i === n) {
      return Math.abs((totalSum - currSum) - currSum);
    }
    const key = i + ',' + currSum;
    if (memo.has(key)) return memo.get(key);
    const include = helper(i + 1, currSum + arr[i]);
    const exclude = helper(i + 1, currSum);
    const res = Math.min(include, exclude);
    memo.set(key, res);
    return res;
  }
  return helper(0, 0);
}

// Test
console.log(minSubsetSumDiff([1, 6, 11, 5])); // Output: 1

Line Notes

const memo = new Map();Initialize memo map for caching

const key = i + ',' + currSum;Create unique key for current state

if (memo.has(key)) return memo.get(key);Return cached result if present

memo.set(key, res);Store computed result for reuse

⏱

Complexity

TimeO(n * total_sum)

SpaceO(n * total_sum) for memo

Memoization reduces exponential calls to polynomial by caching states defined by index and sum

💡 For n=100 and sum=1000, this is about 100,000 states, which is feasible.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for typical constraints.

🧠

Bottom-Up Tabulation

💡 Tabulation builds the solution iteratively, which is often easier to debug and understand than recursion.

Intuition

Use a 2D boolean DP table to track which sums are achievable with subsets of the array.

Algorithm

1. Calculate total sum of array elements.
2. Initialize a 2D DP array dp[n+1][total_sum+1] with False, except dp[0][0] = True.
3. Iterate over elements and sums, updating dp[i][w] based on dp[i-1][w] and dp[i-1][w - arr[i-1]].
4. Find the largest w ≤ total_sum/2 where dp[n][w] is True.
5. Return total_sum - 2*w as minimum difference.

💡 This approach systematically builds all possible sums and picks the best partition.

Recurrence:dp[i][w] = dp[i-1][w] OR dp[i-1][w - arr[i-1]] if w ≥ arr[i-1]

</>

Code

def min_subset_sum_diff(arr):
    total_sum = sum(arr)
    n = len(arr)
    dp = [[False] * (total_sum + 1) for _ in range(n + 1)]
    dp[0][0] = True
    for i in range(1, n + 1):
        for w in range(total_sum + 1):
            dp[i][w] = dp[i-1][w]
            if w >= arr[i-1]:
                dp[i][w] = dp[i][w] or dp[i-1][w - arr[i-1]]
    half = total_sum // 2
    for w in range(half, -1, -1):
        if dp[n][w]:
            return total_sum - 2 * w

# Driver code
if __name__ == '__main__':
    arr = [1, 6, 11, 5]
    print(min_subset_sum_diff(arr))  # Output: 1

Line Notes

dp = [[False] * (total_sum + 1) for _ in range(n + 1)]Initialize DP table for all elements and sums

dp[0][0] = TrueSum 0 is achievable with zero elements

dp[i][w] = dp[i-1][w]Exclude current element, inherit previous possibility

if w >= arr[i-1]:Check if current element can be included for sum w

dp[i][w] = dp[i][w] or dp[i-1][w - arr[i-1]]Include current element if possible

for w in range(half, -1, -1):Find closest sum to half total sum for minimal difference

import java.util.*;
public class MinSubsetSumDiff {
    public static int minSubsetSumDiff(int[] arr) {
        int totalSum = 0;
        for (int num : arr) totalSum += num;
        int n = arr.length;
        boolean[][] dp = new boolean[n + 1][totalSum + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= totalSum; w++) {
                dp[i][w] = dp[i - 1][w];
                if (w >= arr[i - 1]) {
                    dp[i][w] = dp[i][w] || dp[i - 1][w - arr[i - 1]];
                }
            }
        }
        int half = totalSum / 2;
        for (int w = half; w >= 0; w--) {
            if (dp[n][w]) {
                return totalSum - 2 * w;
            }
        }
        return 0;
    }
    public static void main(String[] args) {
        int[] arr = {1, 6, 11, 5};
        System.out.println(minSubsetSumDiff(arr)); // Output: 1
    }
}

Line Notes

boolean[][] dp = new boolean[n + 1][totalSum + 1];DP table for elements and sums

dp[0][0] = true;Sum 0 achievable with no elements

dp[i][w] = dp[i - 1][w];Exclude current element

if (w >= arr[i - 1]) {Check if including current element is possible

dp[i][w] = dp[i][w] || dp[i - 1][w - arr[i - 1]];Include current element if possible

for (int w = half; w >= 0; w--) {Find best partition sum closest to half

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int minSubsetSumDiff(const vector<int>& arr) {
    int totalSum = accumulate(arr.begin(), arr.end(), 0);
    int n = arr.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(totalSum + 1, false));
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= totalSum; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= arr[i - 1]) {
                dp[i][w] = dp[i][w] || dp[i - 1][w - arr[i - 1]];
            }
        }
    }
    int half = totalSum / 2;
    for (int w = half; w >= 0; w--) {
        if (dp[n][w]) {
            return totalSum - 2 * w;
        }
    }
    return 0;
}

int main() {
    vector<int> arr = {1, 6, 11, 5};
    cout << minSubsetSumDiff(arr) << endl; // Output: 1
    return 0;
}

Line Notes

vector<vector<bool>> dp(n + 1, vector<bool>(totalSum + 1, false));Initialize DP table

dp[0][0] = true;Sum 0 achievable with zero elements

dp[i][w] = dp[i - 1][w];Exclude current element

if (w >= arr[i - 1]) {Check if including current element is possible

dp[i][w] = dp[i][w] || dp[i - 1][w - arr[i - 1]];Include current element if possible

for (int w = half; w >= 0; w--) {Find closest sum to half total sum

function minSubsetSumDiff(arr) {
  const totalSum = arr.reduce((a, b) => a + b, 0);
  const n = arr.length;
  const dp = Array.from({ length: n + 1 }, () => Array(totalSum + 1).fill(false));
  dp[0][0] = true;
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= totalSum; w++) {
      dp[i][w] = dp[i - 1][w];
      if (w >= arr[i - 1]) {
        dp[i][w] = dp[i][w] || dp[i - 1][w - arr[i - 1]];
      }
    }
  }
  const half = Math.floor(totalSum / 2);
  for (let w = half; w >= 0; w--) {
    if (dp[n][w]) {
      return totalSum - 2 * w;
    }
  }
  return 0;
}

// Test
console.log(minSubsetSumDiff([1, 6, 11, 5])); // Output: 1

Line Notes

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

dp[0][0] = true;Sum 0 achievable with no elements

dp[i][w] = dp[i - 1][w];Exclude current element

if (w >= arr[i - 1]) {Check if including current element is possible

dp[i][w] = dp[i][w] || dp[i - 1][w - arr[i - 1]];Include current element if possible

for (let w = half; w >= 0; w--) {Find best partition sum closest to half

⏱

Complexity

TimeO(n * total_sum)

SpaceO(n * total_sum)

We fill a DP table of size n by total_sum, iterating over all elements and sums

💡 For n=100 and sum=1000, this is about 100,000 operations, which is efficient.

Interview Verdict: Accepted

Tabulation is a robust and clear approach suitable for interviews.

🧠

Space Optimized Bottom-Up DP

💡 We can reduce space from O(n*sum) to O(sum) by using a single array and iterating sums backwards.

Intuition

Since dp[i][w] depends only on dp[i-1][w] and dp[i-1][w - arr[i-1]], we can use one array and update it in reverse order.

Algorithm

1. Calculate total sum of array elements.
2. Initialize a 1D boolean DP array dp[total_sum+1] with dp[0] = True.
3. Iterate over each element, updating dp array backwards for sums from total_sum down to element value.
4. After processing all elements, find the largest sum ≤ total_sum/2 achievable.
5. Return total_sum - 2 * that sum as the minimum difference.

💡 This approach uses less memory by carefully updating sums in reverse to avoid overwriting needed data.

Recurrence:dp[w] = dp[w] OR dp[w - arr[i]] (iterating w backwards)

</>

Code

def min_subset_sum_diff(arr):
    total_sum = sum(arr)
    n = len(arr)
    dp = [False] * (total_sum + 1)
    dp[0] = True
    for num in arr:
        for w in range(total_sum, num - 1, -1):
            dp[w] = dp[w] or dp[w - num]
    half = total_sum // 2
    for w in range(half, -1, -1):
        if dp[w]:
            return total_sum - 2 * w

# Driver code
if __name__ == '__main__':
    arr = [1, 6, 11, 5]
    print(min_subset_sum_diff(arr))  # Output: 1

Line Notes

dp = [False] * (total_sum + 1)Initialize 1D DP array for sums

dp[0] = TrueSum 0 achievable without elements

for w in range(total_sum, num - 1, -1)Iterate backwards to avoid using updated values in same iteration

dp[w] = dp[w] or dp[w - num]Update achievable sums including current element

for w in range(half, -1, -1)Find closest sum to half total sum

import java.util.*;
public class MinSubsetSumDiff {
    public static int minSubsetSumDiff(int[] arr) {
        int totalSum = 0;
        for (int num : arr) totalSum += num;
        boolean[] dp = new boolean[totalSum + 1];
        dp[0] = true;
        for (int num : arr) {
            for (int w = totalSum; w >= num; w--) {
                dp[w] = dp[w] || dp[w - num];
            }
        }
        int half = totalSum / 2;
        for (int w = half; w >= 0; w--) {
            if (dp[w]) {
                return totalSum - 2 * w;
            }
        }
        return 0;
    }
    public static void main(String[] args) {
        int[] arr = {1, 6, 11, 5};
        System.out.println(minSubsetSumDiff(arr)); // Output: 1
    }
}

Line Notes

boolean[] dp = new boolean[totalSum + 1];1D DP array for sums

dp[0] = true;Sum 0 achievable initially

for (int w = totalSum; w >= num; w--) {Iterate backwards to prevent reuse in same iteration

dp[w] = dp[w] || dp[w - num];Update achievable sums including current element

for (int w = half; w >= 0; w--) {Find best partition sum closest to half

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int minSubsetSumDiff(const vector<int>& arr) {
    int totalSum = accumulate(arr.begin(), arr.end(), 0);
    vector<bool> dp(totalSum + 1, false);
    dp[0] = true;
    for (int num : arr) {
        for (int w = totalSum; w >= num; w--) {
            dp[w] = dp[w] || dp[w - num];
        }
    }
    int half = totalSum / 2;
    for (int w = half; w >= 0; w--) {
        if (dp[w]) {
            return totalSum - 2 * w;
        }
    }
    return 0;
}

int main() {
    vector<int> arr = {1, 6, 11, 5};
    cout << minSubsetSumDiff(arr) << endl; // Output: 1
    return 0;
}

Line Notes

vector<bool> dp(totalSum + 1, false);1D DP array for sums

dp[0] = true;Sum 0 achievable initially

for (int w = totalSum; w >= num; w--) {Iterate backwards to avoid double counting

dp[w] = dp[w] || dp[w - num];Update achievable sums including current element

for (int w = half; w >= 0; w--) {Find closest sum to half total sum

function minSubsetSumDiff(arr) {
  const totalSum = arr.reduce((a, b) => a + b, 0);
  const dp = Array(totalSum + 1).fill(false);
  dp[0] = true;
  for (const num of arr) {
    for (let w = totalSum; w >= num; w--) {
      dp[w] = dp[w] || dp[w - num];
    }
  }
  const half = Math.floor(totalSum / 2);
  for (let w = half; w >= 0; w--) {
    if (dp[w]) {
      return totalSum - 2 * w;
    }
  }
  return 0;
}

// Test
console.log(minSubsetSumDiff([1, 6, 11, 5])); // Output: 1

Line Notes

const dp = Array(totalSum + 1).fill(false);Initialize 1D DP array

dp[0] = true;Sum 0 achievable initially

for (let w = totalSum; w >= num; w--) {Iterate backwards to avoid using updated values

dp[w] = dp[w] || dp[w - num];Update achievable sums including current element

for (let w = half; w >= 0; w--) {Find best partition sum closest to half

⏱

Complexity

TimeO(n * total_sum)

SpaceO(total_sum)

We use a single array of size total_sum and update it for each element

💡 This reduces memory usage significantly while maintaining time efficiency.

Interview Verdict: Accepted

Space optimization is a valuable skill to demonstrate in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 For interviews, coding bottom-up tabulation or space-optimized DP is usually best for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down Memoization	O(n * total_sum)	O(n * total_sum) memo + O(n) stack	Possible for large n	Yes	Good to mention and code if comfortable
3. Bottom-Up Tabulation	O(n * total_sum)	O(n * total_sum)	No	Yes	Preferred approach to code
4. Space Optimized DP	O(n * total_sum)	O(total_sum)	No	Harder but possible with extra bookkeeping	Great to mention as optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem space.Introduce memoization to optimize overlapping subproblems.Present bottom-up tabulation as an iterative alternative.Discuss space optimization to show mastery of DP techniques.Code the chosen approach carefully and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Understanding of recursion and DP, ability to optimize naive solutions, clarity in explaining tradeoffs, and coding accuracy.

Common Follow-ups

• What if array contains zeros or negative numbers? → Adjust DP to handle zero sums or offset negatives.
• Can you reconstruct the subsets? → Use DP table to backtrack and find subset elements.

💡 These follow-ups test deeper understanding and ability to extend solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves partitioning or dividing sets; 2) Minimize difference or balance sums; 3) Subset sums or knapsack style constraints; 4) Requires exploring subsets efficiently.

Signature Phrases

'partition the set into two subsets''minimize the difference between subset sums'

NOT This Pattern When

Problems that ask for maximum sum under constraints without difference minimization are classic knapsack, not this variant.

Similar Problems

Partition Equal Subset Sum - special case where difference is zeroTarget Sum - variation with signs to reach targetSubset Sum - foundational problem to check sum existence

Practice

1. Consider the following Python function implementing the DP with bitmask tabulation approach for partitioning an array into k equal sum subsets. What is the return value when called with nums = [1, 2, 3, 4] and k = 2?

from typing import List

def canPartitionKSubsets(nums: List[int], k: int) -> bool:
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    n = len(nums)
    nums.sort()
    if nums[-1] > target:
        return False

    dp = [-1] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == -1:
            continue
        for i in range(n):
            if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:
                next_mask = mask | (1 << i)
                if dp[next_mask] == -1:
                    dp[next_mask] = (dp[mask] + nums[i]) % target

    return dp[(1 << n) - 1] == 0

easy

A. True

B. False

C. Raises an exception due to index error

D. Returns None

Solution

1. Step 1: Calculate total and target

   Sum is 10, k=2, target subset sum = 5.

2. Step 2: Trace dp updates

   DP explores subsets; for example, {1,4} and {2,3} both sum to 5, so dp[(1<<4)-1] = 0, returning True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Partition exists: [1,4] and [2,3] [OK]

Hint: Sum divisible by k and dp final state 0 means partition possible [OK]

Common Mistakes:

• Confusing dp array indexing or bitmask operations
• Forgetting to check if largest element exceeds target

2. The following code attempts to solve the integer break problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on some inputs?

def integer_break(n):
    dp = [0] * n
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
        dp[i] = max_product
    return dp[n]

medium

A. Line 3: dp[1] = 1 base case initialization

B. Line 2: dp array size is n instead of n+1

C. Line 5: Outer loop range from 2 to n+1

D. Line 7: Using max(j, dp[j]) instead of just dp[j]

Solution

1. Step 1: Check dp array size

   dp is initialized with size n, but indices up to n are accessed (dp[i], dp[i-j]) which requires size n+1.

2. Step 2: Consequences of wrong size

   Accessing dp[n] or dp[i-j] when i=n causes index out of range or incorrect results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   dp array must be size n+1 to safely index up to n [OK]

Hint: Check array size matches max index accessed [OK]

Common Mistakes:

• Forgetting dp size off-by-one
• Misplacing base case initialization

3. What is the time complexity of the space-optimized bottom-up DP solution for Last Stone Weight II, where n is the number of stones and sum is the total weight of all stones?

medium

A. O(n + sum)

B. O(n^2)

C. O(n * sum * log n)

D. O(n * sum)

Solution

1. Step 1: Identify loops in the code

   Outer loop runs n times (for each stone), inner loop runs up to half the total sum (sum/2).

2. Step 2: Calculate total operations

   Each iteration updates dp array, so total operations ≈ n * (sum/2) -> O(n * sum).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP complexity depends on n and sum, not n squared or log factors [OK]

Hint: DP loops over stones and sums -> O(n * sum) [OK]

Common Mistakes:

• Confusing n with sum leading to O(n^2)
• Assuming logarithmic factor due to sorting
• Ignoring that dp array size depends on sum

4. Suppose the problem is modified so that each number in the input array can be used multiple times to form the subsets. Which change to the DP approach correctly solves this variant?

hard

A. Keep the same code but iterate the dp array backwards to avoid reuse of elements

B. Change the inner loop to iterate forwards from num to target to allow multiple uses of the same element

C. Use recursion without memoization to explore all combinations with repeats

D. Double the dp array size to track counts of each element used

Solution

1. Step 1: Understand the difference between 0/1 and unbounded knapsack

   Allowing multiple uses means the problem becomes unbounded knapsack, which requires forward iteration over dp array.

2. Step 2: Identify correct dp iteration direction

   Iterating forwards from num to target allows dp[w] to build upon dp[w - num] updated in the same iteration, enabling multiple uses.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backward iteration prevents multiple uses; forward iteration enables them [OK]

Hint: Forward dp iteration enables multiple uses of elements [OK]

Common Mistakes:

• Using backward iteration from 0/1 knapsack
• Ignoring iteration direction for repeats

5. Suppose the problem is modified so that you want to find the minimum number of perfect squares summing to n, but now each perfect square can only be used at most once. Which of the following changes correctly adapts the algorithm?

hard

A. Keep the same bottom-up DP but iterate squares in increasing order and update dp[i] from dp[i - square] without reuse

B. Use a top-down memoized recursion with a visited set to avoid reusing squares

C. Use a 2D DP array where dp[i][j] represents minimum squares using first j squares to sum to i

D. Change the inner loop to iterate over squares in decreasing order and update dp[i] accordingly

Solution

1. Step 1: Understand the constraint change

   Limiting each perfect square to be used at most once converts the problem from unbounded to 0/1 knapsack variant, requiring tracking which squares are used.

2. Step 2: Identify correct DP adaptation

   A 2D DP array dp[i][j] that tracks minimum squares to sum to i using first j squares correctly models the usage constraint. Other options either do not prevent reuse or do not track usage properly.

3. Step 3: Confirm why other options fail

   Keep the same bottom-up DP but iterate squares in increasing order and update dp[i] from dp[i - square] without reuse still allows reuse implicitly. Use a top-down memoized recursion with a visited set to avoid reusing squares is inefficient and complex. Change the inner loop to iterate over squares in decreasing order and update dp[i] accordingly's order change alone doesn't enforce usage limits.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   0/1 knapsack requires 2D DP to track usage [OK]

Hint: At-most-once usage -> 0/1 knapsack -> 2D DP needed [OK]

Common Mistakes:

• Trying to reuse unbounded DP
• Ignoring usage constraints in DP state