Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogle

Minimum Subset Sum Difference

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(2^n)O(n) recursion stackYes (deep recursion)YesMention only - never code
2. Top-Down MemoizationO(n * total_sum)O(n * total_sum) memo + O(n) stackPossible for large nYesGood to mention and code if comfortable
3. Bottom-Up TabulationO(n * total_sum)O(n * total_sum)NoYesPreferred approach to code
4. Space Optimized DPO(n * total_sum)O(total_sum)NoHarder but possible with extra bookkeepingGreat 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/5)
1. Consider the following Python code for the Equal Partition problem. What is the value of dp[target] after processing the input [1, 5, 11, 5]?
def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for w in range(target, num - 1, -1):
            dp[w] = dp[w] or dp[w - num]

    return dp[target]

print(canPartition([1,5,11,5]))
easy
A. true
B. false
C. null (error occurs)
D. Depends on order of iteration

Solution

  1. Step 1: Calculate total and target

    The total sum is 1 + 5 + 11 + 5 = 22, which is even, so target = 11.
  2. Step 2: Trace dp array updates for each num

    After processing all nums, dp[11] becomes True because subset {11} or {5,5,1} sums to 11.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Input is classic example where partition exists; dp[target] is True [OK]
Hint: Sum is even and dp[target] tracks subset sums [OK]
Common Mistakes:
  • Confusing dp[target] with dp[target-1]
  • Forgetting to iterate backwards in dp update
2. Given the following code, what is the output when coins = [1, 2, 5] and amount = 5?
def count_ways_space_opt(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for w in range(coin, amount + 1):
            dp[w] += dp[w - coin]
    return dp[amount]

coins = [1, 2, 5]
amount = 5
print(count_ways_space_opt(coins, amount))
easy
A. 4
B. 7
C. 5
D. 6

Solution

  1. Step 1: Trace dp array updates for each coin

    Start dp = [1,0,0,0,0,0]. After coin=1, dp = [1,1,1,1,1,1]. After coin=2, dp = [1,1,2,2,3,3]. After coin=5, dp = [1,1,2,2,3,6].
  2. Step 2: Confirm dp[5] value

    dp[5] = 6, representing 6 ways to make amount 5 with coins [1,2,5].
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Manual dp tracing matches output 6 [OK]
Hint: DP accumulates counts incrementally per coin [OK]
Common Mistakes:
  • Off-by-one in dp indexing
  • Miscounting after last coin iteration
  • Confusing permutations with combinations
3. What is the time complexity of the space-optimized bottom-up dynamic programming solution for counting the number of ways to make change with n coins and amount W?
medium
A. O(n * W) because for each coin we iterate over all amounts up to W
B. O(n + W) because we iterate over coins and amounts separately
C. O(W^n) due to nested loops over coins and amounts
D. O(n * W) plus O(W) auxiliary space for the dp array

Solution

  1. Step 1: Identify loops and their ranges

    Outer loop runs n times (coins), inner loop runs up to W (amount), so time is O(n * W).
  2. Step 2: Consider space usage

    DP array size is W+1, so auxiliary space is O(W). Total complexity includes both time and space, but time complexity is the main focus here.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Time O(n*W) matches DP approach [OK]
Hint: Time is product of coins and amount; space is dp array size [OK]
Common Mistakes:
  • Confusing time with space complexity
  • Forgetting auxiliary space for dp array
  • Mistaking exponential complexity for DP
4. Suppose the problem is modified so that each element in the array can be used multiple times (unlimited reuse) to form k equal sum subsets. Which of the following modifications to the DP with bitmask tabulation approach correctly adapts to this change?
hard
A. Use backtracking with memoization on subsets but do not use bitmasking since reuse breaks subset uniqueness
B. Keep the same bitmask DP but allow setting dp[next_mask] multiple times without restriction
C. Replace bitmask DP with a classic unbounded knapsack DP that tracks sums without bitmasking
D. Modify the bitmask DP to reset dp states after each full subset sum is reached to allow reuse

Solution

  1. Step 1: Understand reuse impact

    Allowing unlimited reuse breaks the uniqueness assumption of subsets represented by bitmasks.
  2. Step 2: Identify suitable DP approach

    Classic unbounded knapsack DP tracks sums without bitmasking, correctly handling reuse.
  3. Step 3: Evaluate other options

    Bitmask DP relies on unique element usage; modifying it without removing bitmasking leads to incorrect states.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Unbounded knapsack DP handles reuse correctly [OK]
Hint: Bitmask DP assumes unique usage; reuse needs unbounded knapsack DP [OK]
Common Mistakes:
  • Trying to reuse bitmask DP without removing uniqueness assumption
  • Ignoring that reuse breaks subset partitioning logic
5. Suppose the Target Sum problem is modified so that each number in the array can be used multiple times (unlimited reuse). Which of the following changes correctly adapts the DP solution to this variant?
hard
A. Use a 1D dp array and update dp in forward order for each num to allow reuse
B. Keep the same DP with offset and update dp in reverse order to avoid double counting
C. Use a 2D dp array with dimensions n and sum, but only update dp[i][s] from dp[i-1][s-num]
D. Switch to a brute force recursion since DP cannot handle reuse

Solution

  1. Step 1: Understand reuse impact on DP iteration

    Allowing unlimited reuse means for each num, dp must be updated in forward order so that dp[s-num] includes ways using current num multiple times.
  2. Step 2: Identify correct DP update order

    Backward iteration prevents reuse by only using previous states. Forward iteration accumulates counts correctly for unlimited usage.
  3. Step 3: Evaluate options

    Use a 1D dp array and update dp in forward order for each num to allow reuse correctly updates dp forward. Keep the same DP with offset and update dp in reverse order to avoid double counting backward iteration is for no reuse. Use a 2D dp array with dimensions n and sum, but only update dp[i][s] from dp[i-1][s-num] restricts to previous items only. Switch to a brute force recursion since DP cannot handle reuse is inefficient.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Forward dp update enables multiple usage of same number [OK]
Hint: Forward dp iteration enables unlimited reuse [OK]
Common Mistakes:
  • Using backward iteration which forbids reuse
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard