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. You are given an array of positive integers and a target sum K. You need to find how many subsets of the array sum exactly to K. Which of the following approaches guarantees an optimal solution with polynomial time complexity?

easy

A. Greedy algorithm that picks the largest elements first until the sum reaches or exceeds K

B. Pure recursion that tries all subsets without memoization

C. Dynamic Programming using a bottom-up tabulation approach that counts subsets for all sums up to K

D. Sorting the array and using two pointers to find pairs that sum to K

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all subsets summing to K, which involves exploring combinations, not just pairs or greedy picks.

2. Step 2: Evaluate approaches

   Greedy and two-pointer methods fail because they do not consider all subsets. Pure recursion is correct but exponential. Bottom-up DP efficiently counts subsets for all sums up to K, ensuring polynomial time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP tabulation counts subsets for all sums -> polynomial time [OK]

Hint: Counting subsets with sum K requires DP, not greedy or two-pointer [OK]

Common Mistakes:

• Assuming greedy or two-pointer works for subset sums
• Confusing counting subsets with finding pairs

2. Consider the following Python code that generates all subsets of nums = [1, 2, 3]. What is the value of subset when mask = 5 during the iteration?

easy

A. [1, 3]

B. [2, 3]

C. [1, 2]

D. [3]

Solution

1. Step 1: Convert mask=5 to binary

   5 in binary is 101, meaning bits 0 and 2 are set.

2. Step 2: Map bits to indices in nums

   Bit 0 corresponds to nums[0]=1, bit 2 corresponds to nums[2]=3, so subset = [1, 3].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mask 5 selects elements at positions 0 and 2 -> [1, 3] [OK]

Hint: Mask bits correspond to included elements [OK]

Common Mistakes:

• Off-by-one bit indexing
• Confusing mask bits with element values

3. What is the time complexity of the backtracking solution with frequency counting for the Combination Sum (Reuse Allowed) problem, where N is the number of candidates, T is the target, and M is the minimum candidate value?

medium

A. O(N * T) because each candidate is tried once for each target value.

B. O(2^N) because each candidate can be either included or excluded once.

C. O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M.

D. O(T^N) because for each target value, all candidates are tried in all combinations.

Solution

1. Step 1: Identify recursion depth and branching factor

   The recursion depth is roughly T/M because the smallest candidate can be used up to T/M times. At each level, up to N candidates are considered with multiple counts.

2. Step 2: Calculate total number of recursive calls

   Each candidate can be chosen 0 to max_use times, leading to branching factor roughly N^(T/M + 1). This exponential complexity dominates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Exponential branching with depth proportional to T/M matches O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M. [OK]

Hint: Exponential in target divided by smallest candidate [OK]

Common Mistakes:

• Confusing DP complexity with backtracking
• Ignoring exponential branching due to reuse

4. Identify the bug in the following code snippet that generates subsets iteratively:

medium

A. Modifying subsets in place without copying causes all subsets to be identical

B. Extending result inside the loop causes infinite loop

C. Starting result with [[]] misses the empty subset

D. Using append instead of extend on subsets is incorrect

Solution

1. Step 1: Analyze subset modification

   The code appends num directly to subsets in result, modifying them in place.

2. Step 2: Consequence of in-place modification

   All subsets in result end up referencing the same list, causing duplicates and incorrect subsets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct approach copies subsets before adding new elements [OK]

Hint: Always copy subsets before adding new elements [OK]

Common Mistakes:

• Modifying lists in place
• Extending result inside loop without fix
• Wrong initial result value

5. What is the time complexity of generating all subsets of an array of size n using the bit manipulation approach shown below?

medium

A. O(2^n * n) because for each of the 2^n masks, we check n bits to build the subset

B. O(2^n) because there are 2^n subsets and each subset is generated in constant time

C. O(n^2) because of nested loops over n elements

D. O(n * 2^n) because each of the 2^n subsets requires iterating over n elements

Solution

1. Step 1: Identify outer loop complexity

   The outer loop runs 2^n times, once per subset mask.

2. Step 2: Identify inner loop complexity

   For each mask, the inner loop iterates n times to check each bit.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Total time is 2^n * n due to mask and bit checks [OK]

Hint: Each subset requires checking n bits -> O(n*2^n) [OK]

Common Mistakes:

• Assuming subset generation is O(2^n) ignoring bit checks
• Confusing n^2 with 2^n * n