Combination Sum III (K Numbers to N)

🎯

Combination Sum III (K Numbers to N)

mediumBACKTRACKINGAmazonGoogleFacebook

Imagine you are organizing a team of exactly k members from a pool of candidates numbered 1 to 9, and you want their combined skill levels to sum up to a target number n. How do you find all such unique teams?

💡 This problem is about finding all unique combinations of a fixed size that sum to a target. Beginners often struggle because they try to generate all subsets without pruning or managing combination size, leading to confusion and inefficiency.

📋

Problem Statement

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers without repetition.

1 ≤ k ≤ 91 ≤ n ≤ 60Numbers 1 to 9 can be used only once each in a combination

💡

Example

Input"k = 3, n = 7"

Output[[1,2,4]]

Only one combination of 3 numbers from 1 to 9 sums to 7: 1 + 2 + 4 = 7.

Input"k = 3, n = 9"

Output[[1,2,6],[1,3,5],[2,3,4]]

Three unique combinations of size 3 sum to 9.

• k = 1, n = 10 → [] (no single number from 1 to 9 equals 10)
• k = 9, n = 45 → [[1,2,3,4,5,6,7,8,9]] (all numbers sum to 45)
• k = 0, n = 0 → [[]] (empty combination sums to zero)
• k = 4, n = 1 → [] (sum too small for 4 numbers)

⚠️

Common Mistakes

Not pruning when sum exceeds target

Leads to exploring unnecessary branches, causing timeouts

✅ Add condition to stop recursion if current sum > target

Allowing duplicate numbers in combinations

Results in duplicate combinations in output

✅ Ensure recursion starts from next number (start + 1) to avoid reuse

Not checking combination size before adding to results

Incorrect combinations of wrong size are included

✅ Add condition to check combination size equals k before adding

Modifying combination list without backtracking (pop)

Combination list grows incorrectly, causing wrong results or errors

✅ Always remove last added number after recursive call to backtrack

🧠

Brute Force (Pure Recursion with Backtracking)

💡 Starting with brute force helps understand the problem's search space and how to explore all combinations systematically, even if inefficient.

Intuition

Try every number from 1 to 9, recursively build combinations, and check if the combination size and sum match the requirements.

Algorithm

1. Start from number 1 and try to include it in the current combination.
2. Recursively try next numbers, adding them to the combination if they don't exceed size k or sum n.
3. If combination size equals k and sum equals n, add it to results.
4. Backtrack by removing the last number and try the next candidate.

💡 The recursion tree can be large and confusing, but it systematically tries all possibilities by building combinations step-by-step.

</>

Code

from typing import List

def combinationSum3(k: int, n: int) -> List[List[int]]:
    res = []
    def backtrack(start: int, comb: List[int], total: int):
        if len(comb) == k and total == n:
            res.append(comb[:])
            return
        if len(comb) > k or total > n:
            return
        for i in range(start, 10):
            comb.append(i)
            backtrack(i + 1, comb, total + i)
            comb.pop()
    backtrack(1, [], 0)
    return res

# Driver code
if __name__ == '__main__':
    print(combinationSum3(3, 7))  # Expected: [[1,2,4]]
    print(combinationSum3(3, 9))  # Expected: [[1,2,6],[1,3,5],[2,3,4]]

Line Notes

def combinationSum3(k: int, n: int) -> List[List[int]]:Defines the function signature with input types and output type for clarity.

def backtrack(start: int, comb: List[int], total: int):Helper function to explore combinations starting from 'start' number.

if len(comb) == k and total == n:Base case: if combination size and sum match, add a copy to results.

for i in range(start, 10):Iterate from current start to 9 to avoid duplicates and maintain ascending order.

import java.util.*;

public class CombinationSum3 {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(1, k, n, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int start, int k, int n, List<Integer> comb, List<List<Integer>> res) {
        if (comb.size() == k && n == 0) {
            res.add(new ArrayList<>(comb));
            return;
        }
        if (comb.size() > k || n < 0) return;
        for (int i = start; i <= 9; i++) {
            comb.add(i);
            backtrack(i + 1, k, n - i, comb, res);
            comb.remove(comb.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum3 solver = new CombinationSum3();
        System.out.println(solver.combinationSum3(3, 7)); // [[1, 2, 4]]
        System.out.println(solver.combinationSum3(3, 9)); // [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
    }
}

Line Notes

public List<List<Integer>> combinationSum3(int k, int n) {Main function to initiate backtracking and return results.

if (comb.size() == k && n == 0) {Base case: combination size reached and sum matched exactly.

for (int i = start; i <= 9; i++) {Loop through candidates from current start to 9 to avoid duplicates.

comb.remove(comb.size() - 1);Backtrack by removing last added number to try next candidate.

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

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> comb;
        backtrack(1, k, n, comb, res);
        return res;
    }

private:
    void backtrack(int start, int k, int n, vector<int>& comb, vector<vector<int>>& res) {
        if (comb.size() == k && n == 0) {
            res.push_back(comb);
            return;
        }
        if (comb.size() > k || n < 0) return;
        for (int i = start; i <= 9; i++) {
            comb.push_back(i);
            backtrack(i + 1, k, n - i, comb, res);
            comb.pop_back();
        }
    }
};

int main() {
    Solution sol;
    auto res1 = sol.combinationSum3(3, 7);
    for (auto &v : res1) {
        cout << "[";
        for (int num : v) cout << num << ",";
        cout << "]\n";
    }
    auto res2 = sol.combinationSum3(3, 9);
    for (auto &v : res2) {
        cout << "[";
        for (int num : v) cout << num << ",";
        cout << "]\n";
    }
    return 0;
}

Line Notes

vector<vector<int>> combinationSum3(int k, int n) {Public method to start backtracking and collect results.

if (comb.size() == k && n == 0) {Check if current combination meets size and sum requirements.

for (int i = start; i <= 9; i++) {Iterate candidates from start to 9 to avoid duplicates and maintain order.

comb.pop_back();Backtrack by removing last element to explore other combinations.

function combinationSum3(k, n) {
    const res = [];
    function backtrack(start, comb, total) {
        if (comb.length === k && total === n) {
            res.push([...comb]);
            return;
        }
        if (comb.length > k || total > n) return;
        for (let i = start; i <= 9; i++) {
            comb.push(i);
            backtrack(i + 1, comb, total + i);
            comb.pop();
        }
    }
    backtrack(1, [], 0);
    return res;
}

// Test cases
console.log(combinationSum3(3, 7)); // [[1,2,4]]
console.log(combinationSum3(3, 9)); // [[1,2,6],[1,3,5],[2,3,4]]

Line Notes

function combinationSum3(k, n) {Defines main function to find combinations.

if (comb.length === k && total === n) {Base case: combination size and sum match target.

for (let i = start; i <= 9; i++) {Loop through candidates from current start to 9 to avoid duplicates.

comb.pop();Backtrack by removing last added number to try next possibility.

⏱

Complexity

TimeO(2^9) because each number 1-9 can be either included or excluded

SpaceO(k) for recursion stack and current combination storage

We explore all subsets of numbers 1 to 9, which is 2^9 = 512 subsets, pruning when size or sum constraints fail.

💡 For n=9, this means at most 512 recursive calls, which is manageable but not efficient for larger input ranges.

Interview Verdict: Accepted but not optimal

This approach works for the problem constraints but is inefficient for larger input sizes; it is useful to understand the problem structure.

🧠

Backtracking with Early Pruning

💡 This approach improves brute force by stopping recursion early when the sum or size constraints cannot be met, reducing unnecessary exploration.

Intuition

If the current sum exceeds n or the combination size exceeds k, stop exploring that path immediately to save time.

Algorithm

1. Start from number 1 and try to include it in the current combination.
2. If current sum or size exceeds target, backtrack immediately.
3. Otherwise, recursively try next numbers.
4. Add valid combinations to results when size and sum match.

💡 Pruning reduces the search space drastically, making the algorithm faster and easier to understand.

</>

Code

from typing import List

def combinationSum3(k: int, n: int) -> List[List[int]]:
    res = []
    def backtrack(start: int, comb: List[int], total: int):
        if total > n or len(comb) > k:
            return
        if len(comb) == k and total == n:
            res.append(comb[:])
            return
        for i in range(start, 10):
            comb.append(i)
            backtrack(i + 1, comb, total + i)
            comb.pop()
    backtrack(1, [], 0)
    return res

# Driver code
if __name__ == '__main__':
    print(combinationSum3(3, 7))  # Expected: [[1,2,4]]
    print(combinationSum3(3, 9))  # Expected: [[1,2,6],[1,3,5],[2,3,4]]

Line Notes

if total > n or len(comb) > k:Prune recursion early if sum or size constraints are violated.

if len(comb) == k and total == n:Add valid combination to results when conditions met.

for i in range(start, 10):Iterate candidates from current start to 9 to avoid duplicates.

comb.pop()Backtrack by removing last number to explore other combinations.

import java.util.*;

public class CombinationSum3 {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(1, k, n, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int start, int k, int n, List<Integer> comb, List<List<Integer>> res) {
        if (n < 0 || comb.size() > k) return;
        if (comb.size() == k && n == 0) {
            res.add(new ArrayList<>(comb));
            return;
        }
        for (int i = start; i <= 9; i++) {
            comb.add(i);
            backtrack(i + 1, k, n - i, comb, res);
            comb.remove(comb.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum3 solver = new CombinationSum3();
        System.out.println(solver.combinationSum3(3, 7)); // [[1, 2, 4]]
        System.out.println(solver.combinationSum3(3, 9)); // [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
    }
}

Line Notes

if (n < 0 || comb.size() > k) return;Prune recursion early when sum or size constraints are violated.

if (comb.size() == k && n == 0) {Add valid combination to results when conditions met.

for (int i = start; i <= 9; i++) {Iterate candidates from current start to 9 to avoid duplicates.

comb.remove(comb.size() - 1);Backtrack by removing last number to explore other combinations.

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

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> comb;
        backtrack(1, k, n, comb, res);
        return res;
    }

private:
    void backtrack(int start, int k, int n, vector<int>& comb, vector<vector<int>>& res) {
        if (n < 0 || comb.size() > k) return;
        if (comb.size() == k && n == 0) {
            res.push_back(comb);
            return;
        }
        for (int i = start; i <= 9; i++) {
            comb.push_back(i);
            backtrack(i + 1, k, n - i, comb, res);
            comb.pop_back();
        }
    }
};

int main() {
    Solution sol;
    auto res1 = sol.combinationSum3(3, 7);
    for (auto &v : res1) {
        cout << "[";
        for (int num : v) cout << num << ",";
        cout << "]\n";
    }
    auto res2 = sol.combinationSum3(3, 9);
    for (auto &v : res2) {
        cout << "[";
        for (int num : v) cout << num << ",";
        cout << "]\n";
    }
    return 0;
}

Line Notes

if (n < 0 || comb.size() > k) return;Stop recursion early if sum or size constraints are violated.

if (comb.size() == k && n == 0) {Add valid combination to results when conditions met.

for (int i = start; i <= 9; i++) {Iterate candidates from current start to 9 to avoid duplicates.

comb.pop_back();Backtrack by removing last number to explore other combinations.

function combinationSum3(k, n) {
    const res = [];
    function backtrack(start, comb, total) {
        if (total > n || comb.length > k) return;
        if (comb.length === k && total === n) {
            res.push([...comb]);
            return;
        }
        for (let i = start; i <= 9; i++) {
            comb.push(i);
            backtrack(i + 1, comb, total + i);
            comb.pop();
        }
    }
    backtrack(1, [], 0);
    return res;
}

// Test cases
console.log(combinationSum3(3, 7)); // [[1,2,4]]
console.log(combinationSum3(3, 9)); // [[1,2,6],[1,3,5],[2,3,4]]

Line Notes

if (total > n || comb.length > k) return;Prune recursion early when sum or size constraints are violated.

if (comb.length === k && total === n) {Add valid combination to results when conditions met.

for (let i = start; i <= 9; i++) {Loop through candidates from current start to 9 to avoid duplicates.

comb.pop();Backtrack by removing last number to explore other combinations.

⏱

Complexity

TimeO(2^9) worst case but pruning reduces actual calls

SpaceO(k) for recursion stack and combination storage

Pruning avoids exploring invalid branches, improving runtime over brute force but still exponential in worst case.

💡 Pruning can cut down calls significantly, making the solution practical for this problem's constraints.

Interview Verdict: Accepted and more efficient than brute force

This is the preferred approach in interviews for this problem as it balances clarity and efficiency.

🧠

Backtracking with Sum Bound Optimization

💡 Further optimize by stopping recursion early if the smallest possible sum with remaining numbers cannot reach the target or if the largest possible sum is too small.

Intuition

Use arithmetic series sums to check if continuing recursion can possibly reach the target sum, pruning impossible branches early.

Algorithm

1. Calculate minimum sum possible with remaining numbers to fill combination.
2. Calculate maximum sum possible with remaining numbers to fill combination.
3. If target sum is outside these bounds, prune recursion.
4. Otherwise, proceed with backtracking as before.

💡 This pruning uses math to avoid unnecessary recursion, making the search more efficient.

</>

Code

from typing import List

def combinationSum3(k: int, n: int) -> List[List[int]]:
    res = []
    def backtrack(start: int, comb: List[int], total: int):
        if len(comb) > k or total > n:
            return
        remaining = k - len(comb)
        # Minimum sum of next 'remaining' numbers
        min_sum = (2 * start + remaining - 1) * remaining // 2
        # Maximum sum of next 'remaining' numbers
        max_sum = (2 * 9 - remaining + 1) * remaining // 2
        if total + min_sum > n or total + max_sum < n:
            return
        if len(comb) == k and total == n:
            res.append(comb[:])
            return
        for i in range(start, 10):
            comb.append(i)
            backtrack(i + 1, comb, total + i)
            comb.pop()
    backtrack(1, [], 0)
    return res

# Driver code
if __name__ == '__main__':
    print(combinationSum3(3, 7))  # Expected: [[1,2,4]]
    print(combinationSum3(3, 9))  # Expected: [[1,2,6],[1,3,5],[2,3,4]]

Line Notes

remaining = k - len(comb)Calculate how many numbers still need to be chosen.

min_sum = (2 * start + remaining - 1) * remaining // 2Calculate minimum sum possible with next 'remaining' numbers starting at 'start'.

max_sum = (2 * 9 - remaining + 1) * remaining // 2Calculate maximum sum possible with next 'remaining' numbers from the top end (9 down).

if total + min_sum > n or total + max_sum < n:Prune if target sum cannot be reached with remaining numbers.

import java.util.*;

public class CombinationSum3 {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(1, k, n, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int start, int k, int n, List<Integer> comb, List<List<Integer>> res) {
        if (comb.size() > k || n < 0) return;
        int remaining = k - comb.size();
        int minSum = (2 * start + remaining - 1) * remaining / 2;
        int maxSum = (2 * 9 - remaining + 1) * remaining / 2;
        if (n < minSum || n > maxSum) return;
        if (comb.size() == k && n == 0) {
            res.add(new ArrayList<>(comb));
            return;
        }
        for (int i = start; i <= 9; i++) {
            comb.add(i);
            backtrack(i + 1, k, n - i, comb, res);
            comb.remove(comb.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum3 solver = new CombinationSum3();
        System.out.println(solver.combinationSum3(3, 7)); // [[1, 2, 4]]
        System.out.println(solver.combinationSum3(3, 9)); // [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
    }
}

Line Notes

int remaining = k - comb.size();Calculate how many numbers still need to be chosen.

int minSum = (2 * start + remaining - 1) * remaining / 2;Minimum sum achievable with next 'remaining' numbers starting at 'start'.

int maxSum = (2 * 9 - remaining + 1) * remaining / 2;Maximum sum achievable with next 'remaining' numbers from the top end.

if (n < minSum || n > maxSum) return;Prune recursion if target sum is unreachable with remaining numbers.

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

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> comb;
        backtrack(1, k, n, comb, res);
        return res;
    }

private:
    void backtrack(int start, int k, int n, vector<int>& comb, vector<vector<int>>& res) {
        if (comb.size() > k || n < 0) return;
        int remaining = k - comb.size();
        int minSum = (2 * start + remaining - 1) * remaining / 2;
        int maxSum = (2 * 9 - remaining + 1) * remaining / 2;
        if (n < minSum || n > maxSum) return;
        if (comb.size() == k && n == 0) {
            res.push_back(comb);
            return;
        }
        for (int i = start; i <= 9; i++) {
            comb.push_back(i);
            backtrack(i + 1, k, n - i, comb, res);
            comb.pop_back();
        }
    }
};

int main() {
    Solution sol;
    auto res1 = sol.combinationSum3(3, 7);
    for (auto &v : res1) {
        cout << "[";
        for (int num : v) cout << num << ",";
        cout << "]\n";
    }
    auto res2 = sol.combinationSum3(3, 9);
    for (auto &v : res2) {
        cout << "[";
        for (int num : v) cout << num << ",";
        cout << "]\n";
    }
    return 0;
}

Line Notes

int remaining = k - comb.size();Calculate how many numbers still need to be chosen.

int minSum = (2 * start + remaining - 1) * remaining / 2;Minimum sum achievable with next 'remaining' numbers starting at 'start'.

int maxSum = (2 * 9 - remaining + 1) * remaining / 2;Maximum sum achievable with next 'remaining' numbers from the top end.

if (n < minSum || n > maxSum) return;Prune recursion if target sum is unreachable with remaining numbers.

function combinationSum3(k, n) {
    const res = [];
    function backtrack(start, comb, total) {
        if (comb.length > k || total > n) return;
        const remaining = k - comb.length;
        const minSum = (2 * start + remaining - 1) * remaining / 2;
        const maxSum = (2 * 9 - remaining + 1) * remaining / 2;
        if (total + minSum > n || total + maxSum < n) return;
        if (comb.length === k && total === n) {
            res.push([...comb]);
            return;
        }
        for (let i = start; i <= 9; i++) {
            comb.push(i);
            backtrack(i + 1, comb, total + i);
            comb.pop();
        }
    }
    backtrack(1, [], 0);
    return res;
}

// Test cases
console.log(combinationSum3(3, 7)); // [[1,2,4]]
console.log(combinationSum3(3, 9)); // [[1,2,6],[1,3,5],[2,3,4]]

Line Notes

const remaining = k - comb.length;Calculate how many numbers still need to be chosen.

const minSum = (2 * start + remaining - 1) * remaining / 2;Minimum sum achievable with next 'remaining' numbers starting at 'start'.

const maxSum = (2 * 9 - remaining + 1) * remaining / 2;Maximum sum achievable with next 'remaining' numbers from the top end.

if (total + minSum > n || total + maxSum < n) return;Prune recursion if target sum is unreachable with remaining numbers.

⏱

Complexity

TimeO(2^9) worst case but pruning with bounds reduces calls significantly

SpaceO(k) for recursion stack and combination storage

Bounds pruning cuts off impossible branches early, improving efficiency over simple pruning.

💡 This approach is the most efficient for this problem size and is a good example of combining math with backtracking.

Interview Verdict: Accepted and most efficient backtracking approach

This approach is ideal for interviews as it shows deep understanding and optimization of backtracking.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 3 is best for interviews: it is efficient and shows mastery of pruning and backtracking.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^9)	O(k)	Low (max depth k ≤ 9)	Yes	Mention only - never code due to inefficiency
2. Backtracking with Early Pruning	O(2^9) but fewer calls due to pruning	O(k)	Low	Yes	Good to code if time-constrained; shows pruning knowledge
3. Backtracking with Sum Bound Optimization	O(2^9) worst but practically faster due to bounds pruning	O(k)	Low	Yes	Best approach to code; shows deep understanding and optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, optimize with pruning, and finally discuss bounds pruning for efficiency.

How to Present

Step 1: Clarify the problem constraints and inputs.Step 2: Describe the brute force recursive approach to generate all combinations.Step 3: Introduce pruning to stop exploring invalid paths early.Step 4: Explain sum bound pruning to further optimize the search.Step 5: Code the final optimized solution and test with examples.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of backtracking, pruning techniques, and ability to optimize recursive solutions while maintaining correctness.

Common Follow-ups

• What if numbers can be repeated? → Modify recursion to allow reuse of numbers.
• What if numbers are not limited to 1-9? → Adjust candidate range and pruning accordingly.

💡 These follow-ups test your adaptability and understanding of constraints and how they affect the solution.

🔍

Pattern Recognition

When to Use

1) Need combinations/subsets of fixed size k, 2) Sum constraint on elements, 3) Elements from a small fixed range, 4) No repetition allowed

Signature Phrases

k numbers that add up to nnumbers 1 to 9unique combinations

NOT This Pattern When

Problems where order matters (permutations) or unlimited repeats allowed are different patterns.

Similar Problems

Combination Sum - allows unlimited repeats, no fixed sizeCombination Sum II - fixed size not required, duplicates handled differentlyCombination Sum IV - counts combinations, order matters

Practice

1. You are given an array of integers and need to find the number of subsets whose bitwise OR equals the maximum possible OR value among all subsets. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach selecting elements with highest bits set first

B. Iterative bitmask enumeration generating all subsets and computing their OR

C. Dynamic programming based on subset sums

D. Sorting the array and using two pointers to find max OR subsets

Solution

1. Step 1: Understand the problem requires checking all subsets

   Since the maximum bitwise OR depends on any combination of elements, all subsets must be considered.

2. Step 2: Identify approach that enumerates all subsets efficiently

   Iterative bitmask enumeration systematically generates all subsets and computes their OR, ensuring no subset is missed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask enumeration covers all subsets -> optimal [OK]

Hint: Bitmask enumeration covers all subsets exhaustively [OK]

Common Mistakes:

• Assuming greedy selection suffices for max OR
• Confusing subset sum DP with bitwise OR problem

2. Consider the following Python function that counts subsets with sum K using a space-optimized DP approach. What is the output when called with arr = [1, 2, 3, 3] and K = 6?

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(K, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[K]

print(count_subsets_space_optimized(arr, K))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0,0] since dp[0]=1 and K=6.

2. Step 2: Process each number updating dp

   After processing 1: dp = [1,1,0,0,0,0,0] After 2: dp = [1,1,1,1,0,0,0] After first 3: dp = [1,1,1,2,1,1,1] After second 3: dp = [1,1,1,3,2,2,3]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp[6] = 5 subsets sum to 6 [OK]

Hint: Trace dp updates backward to avoid double counting [OK]

Common Mistakes:

• Forgetting to iterate backward in dp array
• Off-by-one errors in dp indices

3. Consider the following Python function implementing backtracking with bitmask memoization for partitioning an array into k equal sum subsets. Given nums = [4, 3, 2, 3, 5, 2, 1] and k = 4, what is the final return value of canPartitionKSubsets(nums, k)?

easy

A. True

B. False

C. Raises an exception due to index error

D. Returns None

Solution

1. Step 1: Calculate total and target sum

   Total sum is 4+3+2+3+5+2+1=20, target per subset = 20/4=5.

2. Step 2: Trace backtracking with sorted nums

   Sorted nums: [5,4,3,3,2,2,1]. The algorithm finds subsets: {5}, {4,1}, {3,2}, {3,2} all summing to 5, so returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All subsets sum to target, so partition possible [OK]

Hint: Sum divisible by k and backtracking finds valid subsets [OK]

Common Mistakes:

• Miscounting sum or target
• Assuming no solution due to order

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

5. Suppose the problem is modified so that elements can be chosen multiple times (unlimited reuse) to form subsets. Which approach correctly adapts to count the number of max bitwise-OR subsets under this new constraint?

hard

A. Use dynamic programming over OR values with state compression to count combinations

B. Use backtracking with memoization to handle repeated elements and prune search

C. Use the same bitmask enumeration approach since subsets remain finite

D. Sort elements and greedily pick those with highest bits until max OR is reached

Solution

1. Step 1: Recognize infinite subsets due to unlimited reuse

   Bitmask enumeration is infeasible as subsets are infinite with reuse allowed.

2. Step 2: Use DP over OR states to count combinations efficiently

   DP with state compression tracks counts of subsets achieving each OR value, handling reuse.

3. Step 3: Understand greedy or naive backtracking fail due to infinite or redundant subsets

   Greedy misses combinations; naive backtracking is exponential and inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP over OR states handles reuse -> correct and efficient [OK]

Hint: Reuse means infinite subsets -> DP over OR states needed [OK]

Common Mistakes:

• Trying bitmask enumeration despite infinite subsets
• Using greedy approach ignoring subset counts