Partition to K Equal Sum Subsets

🎯

Partition to K Equal Sum Subsets

mediumDPAmazonGoogleFacebook

Imagine you have a set of gifts and want to divide them equally among k friends so that everyone gets the same total value. Can you figure out if such a fair division is possible?

💡 This problem asks if we can split an array into k subsets with equal sums. Beginners often struggle because it combines subset sum logic with partitioning into multiple groups, requiring careful state management and pruning. Think of it as trying to fill k buckets equally without overflowing any.

📋

Problem Statement

Given an array of integers nums and an integer k, determine if it is possible to partition the array into k non-empty subsets whose sums are all equal. Return true if such a partition exists, otherwise false.

1 ≤ nums.length ≤ 161 ≤ nums[i] ≤ 10^41 ≤ k ≤ nums.length

💡

Example

Input"nums = [4, 3, 2, 3, 5, 2, 1], k = 4"

Outputtrue

We can partition into (5), (1,4), (2,3), (2,3) each summing to 5.

Input"nums = [1, 2, 3, 4], k = 3"

Outputfalse

No way to split into 3 subsets with equal sum.

• All elements are equal → should return true
• k equals 1 → always true
• Sum of elements not divisible by k → always false
• Array contains very large numbers → test efficiency and pruning

🔁

Why DP?

Why greedy fails:

A greedy approach might pick the largest elements first to form subsets, but this can fail. For example, nums=[1,1,1,1,2,2,2,2], k=4. Greedy might put all 2s together, leaving 1s that can't form equal sums.

DP state:

dp[mask] = true if the subset of elements represented by 'mask' can be partitioned into subsets summing to the target sum.

Recurrence:dp[mask] = dp[mask] OR dp[mask ^ subset] if sum(subset) == target

If we can partition the remaining elements (mask ^ subset) successfully, and the current subset sums to target, then dp[mask] is true.

⚠️

Common Mistakes

Not checking if total sum is divisible by k

Algorithm wastes time exploring impossible partitions

✅ Add early check: if sum % k != 0 return false

Not sorting nums descending before backtracking

Pruning is less effective, leading to timeouts

✅ Sort nums in descending order to place large elements first

Not pruning symmetric states by breaking when bucket is empty

Explores redundant states, increasing runtime

✅ Break loop when bucket[i] == 0 after trying placement

Incorrect bitmask usage leading to wrong states

Memoization fails, causing wrong answers or infinite recursion

✅ Carefully use bitwise operators to track used elements

Not handling the last bucket case properly in memoization

Algorithm may return false negatives

✅ Return true when count == k-1 since last bucket must be valid

🧠

Brute Force (Backtracking with Subset Sum Checks)

💡 This approach explores all possible ways to assign elements to k buckets. It is slow but helps understand the problem's combinatorial nature and pruning opportunities. Think of it as trying every way to fill k boxes with items, backtracking when a box overflows.

Intuition

Try to put each element into one of the k buckets if it doesn't exceed the target sum. Backtrack if stuck.

Algorithm

1. Calculate total sum and check divisibility by k.
2. Sort nums in descending order to optimize pruning.
3. Recursively try to place each number into any bucket without exceeding target sum.
4. Backtrack if no valid placement is found.

💡 The recursion tree explores all assignments, pruning when sums exceed target, which is key to reducing search space.

Recurrence:Not applicable for pure backtracking without memoization.

</>

Code

from typing import List

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

    def backtrack(index):
        if index == len(nums):
            return all(b == target for b in buckets)
        for i in range(k):
            if buckets[i] + nums[index] <= target:
                buckets[i] += nums[index]
                if backtrack(index + 1):
                    return True
                buckets[i] -= nums[index]
            if buckets[i] == 0:
                break
        return False

    return backtrack(0)

# Driver code
if __name__ == '__main__':
    print(canPartitionKSubsets([4,3,2,3,5,2,1], 4))  # True
    print(canPartitionKSubsets([1,2,3,4], 3))        # False

Line Notes

total = sum(nums)Calculate total sum to check divisibility by k early

nums.sort(reverse=True)Sort descending to place large numbers first, improving pruning

for i in range(k)Try placing current number in each bucket

if buckets[i] + nums[index] <= targetOnly place if it doesn't exceed target sum

if buckets[i] == 0:Break early to avoid redundant symmetric states

import java.util.Arrays;

public class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % k != 0) return false;
        int target = total / k;
        Arrays.sort(nums);
        // Sort descending for pruning
        for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        int n = nums.length;
        int[] buckets = new int[k];
        return backtrack(nums, 0, buckets, target);
    }

    private boolean backtrack(int[] nums, int index, int[] buckets, int target) {
        if (index == nums.length) {
            for (int b : buckets) if (b != target) return false;
            return true;
        }
        int num = nums[index];
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] + num <= target) {
                buckets[i] += num;
                if (backtrack(nums, index + 1, buckets, target)) return true;
                buckets[i] -= num;
            }
            if (buckets[i] == 0) break;
        }
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.canPartitionKSubsets(new int[]{4,3,2,3,5,2,1}, 4)); // true
        System.out.println(sol.canPartitionKSubsets(new int[]{1,2,3,4}, 3)); // false
    }
}

Line Notes

int total = 0;Sum all elements to check divisibility

Arrays.sort(nums);Sort ascending initially

// Sort descending for pruningReverse array to descending order for better pruning

for (int i = 0; i < buckets.length; i++)Try placing current number in each bucket

if (buckets[i] + num <= target)Only place if sum does not exceed target

if (buckets[i] == 0) break;Avoid symmetric states by pruning early

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

bool backtrack(vector<int>& nums, int index, vector<int>& buckets, int target) {
    if (index == nums.size()) {
        for (int b : buckets) if (b != target) return false;
        return true;
    }
    int num = nums[index];
    for (int i = 0; i < buckets.size(); i++) {
        if (buckets[i] + num <= target) {
            buckets[i] += num;
            if (backtrack(nums, index + 1, buckets, target)) return true;
            buckets[i] -= num;
        }
        if (buckets[i] == 0) break;
    }
    return false;
}

bool canPartitionKSubsets(vector<int>& nums, int k) {
    int total = 0;
    for (int num : nums) total += num;
    if (total % k != 0) return false;
    int target = total / k;
    sort(nums.begin(), nums.end());
    // Reverse to descending order for pruning
    reverse(nums.begin(), nums.end());
    vector<int> buckets(k, 0);
    return backtrack(nums, 0, buckets, target);
}

int main() {
    vector<int> nums1 = {4,3,2,3,5,2,1};
    cout << (canPartitionKSubsets(nums1, 4) ? "true" : "false") << endl; // true
    vector<int> nums2 = {1,2,3,4};
    cout << (canPartitionKSubsets(nums2, 3) ? "true" : "false") << endl; // false
    return 0;
}

Line Notes

int total = 0;Sum elements to check divisibility

sort(nums.begin(), nums.end());Sort ascending initially

// Reverse to descending order for pruningReverse array to descending order for better pruning

for (int i = 0; i < buckets.size(); i++)Try placing current number in each bucket

if (buckets[i] + num <= target)Only place if sum does not exceed target

if (buckets[i] == 0) break;Prune symmetric states to reduce search

function canPartitionKSubsets(nums, k) {
    const total = nums.reduce((a,b) => a + b, 0);
    if (total % k !== 0) return false;
    const target = total / k;
    nums.sort((a,b) => b - a);
    const buckets = new Array(k).fill(0);

    function backtrack(index) {
        if (index === nums.length) {
            return buckets.every(b => b === target);
        }
        for (let i = 0; i < k; i++) {
            if (buckets[i] + nums[index] <= target) {
                buckets[i] += nums[index];
                if (backtrack(index + 1)) return true;
                buckets[i] -= nums[index];
            }
            if (buckets[i] === 0) break;
        }
        return false;
    }

    return backtrack(0);
}

// Test cases
console.log(canPartitionKSubsets([4,3,2,3,5,2,1], 4)); // true
console.log(canPartitionKSubsets([1,2,3,4], 3)); // false

Line Notes

const total = nums.reduce((a,b) => a + b, 0);Sum all elements to check divisibility

nums.sort((a,b) => b - a);Sort descending to place large numbers first

for (let i = 0; i < k; i++)Try placing current number in each bucket

if (buckets[i] + nums[index] <= target)Only place if sum does not exceed target

if (buckets[i] === 0) break;Prune symmetric states to reduce redundant work

⏱

Complexity

TimeO(k^n) in worst case due to trying all assignments

SpaceO(n) recursion stack and O(k) buckets array

Each element can go into any of k buckets, leading to k^n possibilities; pruning reduces this but worst case remains exponential.

💡 For n=10 and k=4, this could mean up to 1 million tries, which is slow but manageable for small inputs.

Interview Verdict: Use only to introduce problem and intuition; too slow for large inputs.

Shows problem structure but not efficient enough for interviews; good for initial explanation.

🧠

Backtracking with Memoization (Bitmask DP)

💡 Memoization avoids recomputing states by caching results for subsets already checked, drastically improving performance over pure backtracking. It leverages bitmasking to represent subsets efficiently.

Intuition

Represent chosen elements as a bitmask and store results of subproblems to avoid repeated work.

Algorithm

1. Calculate total sum and target per subset.
2. Use a bitmask to represent which elements are used.
3. Recursively try to fill buckets, caching results for each bitmask state.
4. Return true if all elements are used and buckets are correctly filled.

💡 Memoization prunes the exponential search by remembering failed or successful states, avoiding duplicate work.

Recurrence:dp[mask] = true if there exists a subset of unused elements forming a bucket and dp[mask | subset] is true

</>

Code

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(reverse=True)
    if nums[0] > target:
        return False

    memo = {}

    def backtrack(used, curr_sum, count):
        if count == k - 1:
            return True
        if curr_sum == target:
            res = backtrack(used, 0, count + 1)
            memo[used] = res
            return res
        if used in memo:
            return memo[used]

        for i in range(n):
            if not (used & (1 << i)) and curr_sum + nums[i] <= target:
                if backtrack(used | (1 << i), curr_sum + nums[i], count):
                    return True
        memo[used] = False
        return False

    return backtrack(0, 0, 0)

# Driver code
if __name__ == '__main__':
    print(canPartitionKSubsets([4,3,2,3,5,2,1], 4))  # True
    print(canPartitionKSubsets([1,2,3,4], 3))        # False

Line Notes

memo = {}Cache results for each bitmask to avoid recomputation

if count == k - 1:If k-1 buckets formed, last bucket must be valid

if curr_sum == target:Start filling next bucket when current bucket is full

if not (used & (1 << i))Check if element i is unused in current mask

memo[used] = FalseMark current state as unsolvable to prune future calls

import java.util.Arrays;
import java.util.HashMap;

public class Solution {
    private int[] nums;
    private int target, n, k;
    private HashMap<Integer, Boolean> memo = new HashMap<>();

    public boolean canPartitionKSubsets(int[] nums, int k) {
        this.nums = nums;
        this.k = k;
        int total = 0;
        for (int num : nums) total += num;
        if (total % k != 0) return false;
        target = total / k;
        n = nums.length;
        Arrays.sort(nums);
        // Reverse to descending order
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        if (nums[0] > target) return false;
        return backtrack(0, 0, 0);
    }

    private boolean backtrack(int used, int currSum, int count) {
        if (count == k - 1) return true;
        if (currSum == target) {
            boolean res = backtrack(used, 0, count + 1);
            memo.put(used, res);
            return res;
        }
        if (memo.containsKey(used)) return memo.get(used);

        for (int i = 0; i < n; i++) {
            if ((used & (1 << i)) == 0 && currSum + nums[i] <= target) {
                if (backtrack(used | (1 << i), currSum + nums[i], count)) return true;
            }
        }
        memo.put(used, false);
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.canPartitionKSubsets(new int[]{4,3,2,3,5,2,1}, 4)); // true
        System.out.println(sol.canPartitionKSubsets(new int[]{1,2,3,4}, 3)); // false
    }
}

Line Notes

private HashMap<Integer, Boolean> memo = new HashMap<>();Memoize results for bitmask states

if (count == k - 1) return true;Last bucket must be valid if others are formed

if (currSum == target)Move to next bucket when current bucket is full

if ((used & (1 << i)) == 0)Check if element i is unused

memo.put(used, false);Cache failure to prune future calls

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

class Solution {
    vector<int> nums;
    int target, n, k;
    unordered_map<int, bool> memo;

    bool backtrack(int used, int currSum, int count) {
        if (count == k - 1) return true;
        if (currSum == target) {
            bool res = backtrack(used, 0, count + 1);
            memo[used] = res;
            return res;
        }
        if (memo.count(used)) return memo[used];

        for (int i = 0; i < n; i++) {
            if (!(used & (1 << i)) && currSum + nums[i] <= target) {
                if (backtrack(used | (1 << i), currSum + nums[i], count)) return true;
            }
        }
        memo[used] = false;
        return false;
    }

public:
    bool canPartitionKSubsets(vector<int>& nums_, int k_) {
        nums = nums_;
        k = k_;
        n = nums.size();
        int total = 0;
        for (int num : nums) total += num;
        if (total % k != 0) return false;
        target = total / k;
        sort(nums.rbegin(), nums.rend());
        if (nums[0] > target) return false;
        return backtrack(0, 0, 0);
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {4,3,2,3,5,2,1};
    cout << (sol.canPartitionKSubsets(nums1, 4) ? "true" : "false") << endl; // true
    vector<int> nums2 = {1,2,3,4};
    cout << (sol.canPartitionKSubsets(nums2, 3) ? "true" : "false") << endl; // false
    return 0;
}

Line Notes

unordered_map<int, bool> memo;Memoize bitmask states to avoid recomputation

if (count == k - 1) return true;Last bucket must be valid if others are formed

if (currSum == target)Start filling next bucket when current bucket is full

if (!(used & (1 << i)))Check if element i is unused

memo[used] = false;Cache failure to prune future calls

function canPartitionKSubsets(nums, k) {
    const total = nums.reduce((a,b) => a + b, 0);
    if (total % k !== 0) return false;
    const target = total / k;
    const n = nums.length;
    nums.sort((a,b) => b - a);
    if (nums[0] > target) return false;
    const memo = new Map();

    function backtrack(used, currSum, count) {
        if (count === k - 1) return true;
        if (currSum === target) {
            const res = backtrack(used, 0, count + 1);
            memo.set(used, res);
            return res;
        }
        if (memo.has(used)) return memo.get(used);

        for (let i = 0; i < n; i++) {
            if (((used >> i) & 1) === 0 && currSum + nums[i] <= target) {
                if (backtrack(used | (1 << i), currSum + nums[i], count)) return true;
            }
        }
        memo.set(used, false);
        return false;
    }

    return backtrack(0, 0, 0);
}

// Test cases
console.log(canPartitionKSubsets([4,3,2,3,5,2,1], 4)); // true
console.log(canPartitionKSubsets([1,2,3,4], 3)); // false

Line Notes

const memo = new Map();Memoize bitmask states to avoid recomputation

if (count === k - 1) return true;Last bucket must be valid if others are formed

if (currSum === target)Start filling next bucket when current bucket is full

if (((used >> i) & 1) === 0)Check if element i is unused

memo.set(used, false);Cache failure to prune future calls

⏱

Complexity

TimeO(n * 2^n) due to memoization over subsets

SpaceO(2^n) for memo and O(n) recursion stack

Memoization reduces repeated exploration of subsets, but all subsets may still be visited.

💡 For n=16, 2^16=65536 states, which is feasible with pruning and memoization.

Interview Verdict: Accepted and efficient for constraints; good interview approach.

Shows mastery of bitmask DP and memoization, a common FAANG technique.

🧠

DP with Bitmask Tabulation

💡 This approach uses bottom-up DP with bitmasks to build solutions from smaller subsets to larger, avoiding recursion overhead. It tracks partial sums modulo target to know when a bucket is complete.

Intuition

Use a DP array indexed by bitmask representing subsets; dp[mask] = current sum mod target if subset can be formed.

Algorithm

1. Calculate total sum and target per bucket.
2. Initialize dp array of size 2^n with -1, dp[0] = 0.
3. For each subset mask, try adding unused elements if sum does not exceed target.
4. If dp[(1<<n)-1] != -1, return true; else false.

💡 Tabulation ensures all smaller subsets are computed before larger ones, enabling safe transitions.

Recurrence:dp[next_mask] = (dp[mask] + nums[i]) % target if dp[mask] != -1 and nums[i] fits

</>

Code

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

# Driver code
if __name__ == '__main__':
    print(canPartitionKSubsets([4,3,2,3,5,2,1], 4))  # True
    print(canPartitionKSubsets([1,2,3,4], 3))        # False

Line Notes

dp = [-1] * (1 << n)Initialize dp array with -1 meaning unreachable states

dp[0] = 0Empty subset sum is zero

if dp[mask] == -1: continueSkip unreachable subsets

if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= targetTry adding unused element if sum fits

if dp[next_mask] == -1:Update dp only if next state is not already reached

dp[next_mask] = (dp[mask] + nums[i]) % targetUpdate dp with new subset sum modulo target

import java.util.Arrays;

public class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % k != 0) return false;
        int target = total / k;
        int n = nums.length;
        Arrays.sort(nums);
        if (nums[n - 1] > target) return false;

        int size = 1 << n;
        int[] dp = new int[size];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int mask = 0; mask < size; mask++) {
            if (dp[mask] == -1) continue;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0 && dp[mask] + nums[i] <= target) {
                    int nextMask = mask | (1 << i);
                    if (dp[nextMask] == -1) {
                        dp[nextMask] = (dp[mask] + nums[i]) % target;
                    }
                }
            }
        }

        return dp[size - 1] == 0;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.canPartitionKSubsets(new int[]{4,3,2,3,5,2,1}, 4)); // true
        System.out.println(sol.canPartitionKSubsets(new int[]{1,2,3,4}, 3)); // false
    }
}

Line Notes

int[] dp = new int[size];DP array to store subset sums modulo target

Arrays.fill(dp, -1);Initialize unreachable states with -1

dp[0] = 0;Empty subset sum is zero

if ((mask & (1 << i)) == 0 && dp[mask] + nums[i] <= target)Try adding unused element if sum fits

if (dp[nextMask] == -1)Update dp only if next state is not already reached

dp[nextMask] = (dp[mask] + nums[i]) % target;Update dp with new subset sum modulo target

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

bool canPartitionKSubsets(vector<int>& nums, int k) {
    int total = 0;
    for (int num : nums) total += num;
    if (total % k != 0) return false;
    int target = total / k;
    int n = nums.size();
    sort(nums.begin(), nums.end());
    if (nums[n - 1] > target) return false;

    int size = 1 << n;
    vector<int> dp(size, -1);
    dp[0] = 0;

    for (int mask = 0; mask < size; mask++) {
        if (dp[mask] == -1) continue;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0 && dp[mask] + nums[i] <= target) {
                int nextMask = mask | (1 << i);
                if (dp[nextMask] == -1) {
                    dp[nextMask] = (dp[mask] + nums[i]) % target;
                }
            }
        }
    }

    return dp[size - 1] == 0;
}

int main() {
    vector<int> nums1 = {4,3,2,3,5,2,1};
    cout << (canPartitionKSubsets(nums1, 4) ? "true" : "false") << endl; // true
    vector<int> nums2 = {1,2,3,4};
    cout << (canPartitionKSubsets(nums2, 3) ? "true" : "false") << endl; // false
    return 0;
}

Line Notes

vector<int> dp(size, -1);Initialize dp with -1 for unreachable states

dp[0] = 0;Empty subset sum is zero

if ((mask & (1 << i)) == 0 && dp[mask] + nums[i] <= target)Try adding unused element if sum fits

if (dp[nextMask] == -1)Update dp only if next state is not already reached

dp[nextMask] = (dp[mask] + nums[i]) % target;Update dp with new subset sum modulo target

if (dp[mask] == -1) continue;Skip unreachable subsets

function canPartitionKSubsets(nums, k) {
    const total = nums.reduce((a,b) => a + b, 0);
    if (total % k !== 0) return false;
    const target = total / k;
    const n = nums.length;
    nums.sort((a,b) => a - b);
    if (nums[n - 1] > target) return false;

    const size = 1 << n;
    const dp = new Array(size).fill(-1);
    dp[0] = 0;

    for (let mask = 0; mask < size; mask++) {
        if (dp[mask] === -1) continue;
        for (let i = 0; i < n; i++) {
            if (((mask & (1 << i)) === 0) && dp[mask] + nums[i] <= target) {
                const nextMask = mask | (1 << i);
                if (dp[nextMask] === -1) {
                    dp[nextMask] = (dp[mask] + nums[i]) % target;
                }
            }
        }
    }

    return dp[size - 1] === 0;
}

// Test cases
console.log(canPartitionKSubsets([4,3,2,3,5,2,1], 4)); // true
console.log(canPartitionKSubsets([1,2,3,4], 3)); // false

Line Notes

const dp = new Array(size).fill(-1);Initialize dp with -1 for unreachable states

dp[0] = 0;Empty subset sum is zero

if (((mask & (1 << i)) === 0) && dp[mask] + nums[i] <= target)Try adding unused element if sum fits

if (dp[nextMask] === -1)Update dp only if next state is not already reached

dp[nextMask] = (dp[mask] + nums[i]) % target;Update dp with new subset sum modulo target

if (dp[mask] === -1) continue;Skip unreachable subsets

⏱

Complexity

TimeO(n * 2^n) due to iterating all subsets and elements

SpaceO(2^n) for dp array

We compute dp for all subsets, each checking n elements for transitions.

💡 For n=16, 2^16=65536 states, which is feasible with efficient implementation.

Interview Verdict: Accepted and efficient; good for interview coding.

Shows bottom-up DP mastery and bitmask usage, a strong interview skill.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoized backtracking or bottom-up DP are best for interviews; brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(k^n)	O(n + k)	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Memoization	O(n * 2^n)	O(2^n)	Possible but less likely	Yes	Code this for medium constraints
3. DP with Bitmask Tabulation	O(n * 2^n)	O(2^n)	No	Yes, with extra tracking	Optimal approach; code if comfortable with bottom-up DP

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when to use each in interviews.

How to Present

Clarify problem constraints and ask about input sizes.Explain brute force backtracking to show understanding of problem structure.Introduce memoization to optimize repeated states.Present bottom-up DP for optimal performance.Discuss pruning and sorting to improve efficiency.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 15min → Test: 3min. Total ~25min

What the Interviewer Tests

Ability to identify exponential search space, optimize with memoization, and implement bitmask DP correctly.

Common Follow-ups

• What if k=2? → Use subset sum partition logic.
• Can you reconstruct the subsets? → Track choices during DP or backtracking.

💡 These follow-ups test deeper understanding of partitioning and solution reconstruction.

🔍

Pattern Recognition

When to Use

1) Asked to partition array into k subsets, 2) Equal sum subsets, 3) Constraints allow bitmasking, 4) Need to check feasibility

Signature Phrases

'partition into k subsets with equal sum''can the array be divided into k groups with equal sum'

NOT This Pattern When

Problems asking for maximum sum subsets without equal partitioning are different.

Similar Problems

Partition Equal Subset Sum - special case with k=2Subset Sum - foundational problem for subset feasibility

Practice

1. Consider the following Python code for counting the number of ways to make change. What is the output when calling change(5, [1, 2, 5])?

easy

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0] since dp[0]=1.

2. Step 2: Update dp for each coin

   For coin=1: dp becomes [1,1,1,1,1,1]; for coin=2: dp updates to [1,1,2,2,3,3]; for coin=5: dp updates to [1,1,2,2,3,4].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   dp[5] = 4 matches known output [OK]

Hint: Trace dp updates coin by coin [OK]

Common Mistakes:

• Off-by-one in dp indexing
• Confusing permutations with combinations

2. You are given a list of jobs where each job has a start time, an end time, and a profit. You want to schedule jobs to maximize total profit such that no two jobs overlap. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming with jobs sorted by end time and binary search to find compatible jobs

B. Pure brute force recursion checking all subsets of jobs

C. Greedy algorithm that always picks the job with the earliest end time

D. Dynamic programming based on sorting jobs by start time and using prefix sums

Solution

1. Step 1: Understand job scheduling constraints

   The problem requires selecting non-overlapping jobs to maximize profit, which is a classic weighted interval scheduling problem.

2. Step 2: Identify the optimal approach

   Sorting jobs by end time allows binary searching for the last compatible job, enabling a DP solution that builds optimal profit incrementally.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy fails on overlapping jobs with higher profit; DP with binary search handles all cases optimally [OK]

Hint: Sort by end time and use DP with binary search [OK]

Common Mistakes:

• Assuming greedy by earliest end time always works
• Sorting by start time only
• Trying brute force without pruning

3. You are given a list of days when you will travel and three types of tickets with different durations and costs. You want to minimize the total cost to cover all travel days. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming using bottom-up tabulation with binary search to find the next uncovered day

B. Greedy algorithm that always buys the cheapest ticket for the current day

C. Pure recursion without memoization, exploring all ticket combinations

D. Sorting days and using a sliding window to pick tickets covering maximum days

Solution

1. Step 1: Understand problem constraints

   The problem requires covering all travel days with minimum cost, where tickets have different durations and costs.

2. Step 2: Identify suitable algorithm

   Greedy fails because cheapest ticket today may not cover future days optimally. Pure recursion is exponential and inefficient. Sliding window doesn't handle overlapping durations well. Bottom-up DP with binary search efficiently finds next uncovered day and computes minimal cost.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP with binary search ensures optimal substructure and efficient lookup [OK]

Hint: Optimal solution requires DP with binary search [OK]

Common Mistakes:

• Assuming greedy always works
• Ignoring overlapping ticket durations
• Using recursion without memoization

4. 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

5. The following code attempts to solve the Target Sum problem using bottom-up DP with offset indexing. Which line contains a subtle bug that causes incorrect results on inputs containing zero?

medium

A. Line 12-15: Updating dp array in-place instead of using a separate next_dp

B. Line 6: dp[offset] = 1

C. Line 10: if dp[s] != 0:

D. Line 8: for num in nums:

Solution

1. Step 1: Identify DP update method

   The code updates dp in-place during iteration over sums, causing double counting when num=0 or overlapping states.

2. Step 2: Understand impact on zero values

   Zero does not change sum, so updating dp in-place doubles counts incorrectly. Using a separate next_dp array avoids this.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   In-place updates cause state reuse within iteration, breaking correctness [OK]

Hint: In-place dp updates cause double counting with zero values [OK]

Common Mistakes:

• Not using a separate dp array for next iteration