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 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. You are given a set of sticks with various lengths. The goal is to determine if these sticks can be arranged to form a perfect square, using all sticks exactly once. Which algorithmic approach is most suitable to guarantee an optimal solution for this problem?

easy

A. Backtracking with bitmasking and memoization to explore all subsets efficiently while pruning invalid paths.

B. Greedy algorithm that always picks the longest stick first and tries to form sides sequentially.

C. Dynamic programming based on subset sums without pruning or memoization.

D. Simple brute force recursion that tries all possible assignments of sticks to sides without optimization.

Solution

1. Step 1: Understand problem constraints

   The problem requires using all sticks exactly once to form four equal sides, which is a partitioning problem with strict constraints.

2. Step 2: Identify suitable algorithm

   Greedy approaches fail because local choices don't guarantee global feasibility. Simple brute force is correct but inefficient. DP without pruning is too slow. Backtracking with bitmask and memoization efficiently explores subsets and prunes invalid paths, guaranteeing optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask + memoization prunes repeated states [OK]

Hint: Bitmask + memoization prunes repeated states [OK]

Common Mistakes:

• Assuming greedy always works for partitioning
• Confusing DP without pruning as efficient
• Ignoring memoization benefits

3. Given the following code to generate subsets, what is the value of result after processing num=2 when nums = [1, 2]?

easy

A. [[], [1], [2]]

B. [[], [1], [1, 2], [2]]

C. [[], [1], [2], [1, 2], [2, 2]]

D. [[], [1], [2], [1, 2]]

Solution

1. Step 1: Trace result after processing num=1

   Initially result = [[]]. After num=1, new_subsets = [[1]], result = [[], [1]].

2. Step 2: Trace result after processing num=2

   For each subset in [[], [1]], add 2: new_subsets = [[2], [1, 2]]. Extend result: [[], [1], [2], [1, 2]].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All subsets of [1,2] are present exactly once [OK]

Hint: Iterative subsets double result size each iteration [OK]

Common Mistakes:

• Forgetting to add subsets with current num
• Appending duplicates
• Wrong order of subsets

4. What is the time complexity of the iterative lexicographic combinations generation algorithm for generating all combinations of size k from n elements?

medium

A. O(n^k) because each element can be chosen or not

B. O(k * (n choose k)) since each combination of size k is generated once and updated in O(k)

C. O(\u03C3(n choose k) * k) where \u03C3 is the number of combinations generated

D. O(n * k) because the outer loop runs n times and inner loop k times

Solution

1. Step 1: Identify number of combinations

   There are exactly (n choose k) combinations to generate.

2. Step 2: Analyze per-combination cost

   Each combination is generated and updated in O(k) time due to copying and resetting elements.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time is proportional to number of combinations times combination size [OK]

Hint: Time depends on number of combinations times k [OK]

Common Mistakes:

• Confusing with exponential O(n^k) or linear O(n*k) complexities

5. What is the time complexity of the optimal iterative approach for generating all unique subsets from an array of length n that may contain duplicates?

medium

A. O(n^2) because of nested loops over the array

B. O(2^n) since each element doubles the subsets

C. O(2^n * n) due to generating all subsets and copying them

D. O(n * 2^n) because sorting dominates the complexity

Solution

1. Step 1: Identify main operations affecting complexity

   Sorting takes O(n log n), which is dominated by subset generation. The algorithm generates all subsets (2^n) and copies subsets of average length O(n).

2. Step 2: Calculate total time complexity

   Generating all subsets is O(2^n), and copying each subset of length up to n leads to O(2^n * n) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Copying subsets causes the extra factor n, not just 2^n [OK]

Hint: Copying subsets adds factor n to 2^n subsets [OK]

Common Mistakes:

• Ignoring subset copying cost and saying O(2^n)
• Confusing sorting cost as dominant
• Mistaking nested loops as O(n^2)