Combination Sum III (K Numbers to N)

📋

Problem

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?

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

Edge cases: 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)

</>

IDE

def combinationSum3(k: int, n: int) -> list:public List<List<Integer>> combinationSum3(int k, int n)vector<vector<int>> combinationSum3(int k, int n)function combinationSum3(k, n)

def combinationSum3(k: int, n: int) -> list:
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> combinationSum3(int k, int n) {
    // Write your solution here
    return {};
}

function combinationSum3(k, n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[1,2],[3,4]]Returned combinations of incorrect size (less than k).✅ Add condition to only append combinations when len(comb) == k and sum == n.

Wrong: [[1,2,4],[1,2,4]]Duplicate combinations due to not incrementing start index properly.✅ Increment start index in recursive call to avoid reusing same numbers.

Wrong: [[9,8,7]]Greedy approach picking largest numbers first, missing other valid combinations.✅ Use backtracking to explore all combinations, not just greedy picks.

Wrong: [[1,2,3,4]]Returned combinations when sum is less than n due to missing sum check.✅ Add condition to prune branches where sum != n when combination size == k.

Wrong: Timeout or no outputNo pruning causing exponential blowup.✅ Add pruning conditions to stop recursion when sum > n or len(comb) > k.

✓

Test Cases

Focus on handling edge cases like empty input and boundary sums.

Watch out for common algorithmic traps like greedy selection and repeated elements.

Optimize your backtracking with pruning to handle the largest inputs efficiently.

t1_01basic

Input{"k":3,"n":7}

Expected[[1,2,4]]

⏱ Performance - must finish in 2000ms

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

💡 Try backtracking by choosing numbers from 1 to 9 without repetition.

💡 Use recursion to build combinations of size k and check if their sum equals n.

💡 Stop exploring a path if the combination size exceeds k or sum exceeds n.

Why it failed: Returned incorrect combinations or missed valid ones. Ensure you only add combinations of size k whose sum equals n, and avoid duplicates by incrementing start index.

✓ Correctly found all unique combinations of size k summing to n.

t1_02basic

Input{"k":3,"n":9}

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

⏱ Performance - must finish in 2000ms

Three combinations of 3 numbers from 1 to 9 sum to 9: [1,2,6], [1,3,5], and [2,3,4].

💡 Enumerate combinations of size k and check their sums.

💡 Use backtracking with pruning when sum exceeds n or combination size exceeds k.

💡 Increment start index to avoid reusing numbers and duplicates.

Why it failed: Missed some valid combinations or included invalid ones. Check that you only add combinations of exact size k and sum n, and avoid reusing numbers.

✓ All valid combinations of size k summing to n found without duplicates.

t2_01edge

Input{"k":0,"n":0}

Expected[[]]

⏱ Performance - must finish in 2000ms

Empty combination is the only valid combination when k=0 and n=0.

💡 Consider the base case where no numbers are chosen and sum is zero.

💡 Return [[]] when k=0 and n=0 as a valid combination.

💡 Ensure your code handles k=0 correctly without errors.

Why it failed: Returned empty list instead of [[]]. Fix by returning [[]] when k=0 and n=0 to represent the empty combination.

✓ Correctly handles empty combination case.

t2_02edge

Input{"k":1,"n":10}

Expected[]

⏱ Performance - must finish in 2000ms

No single number from 1 to 9 equals 10, so no valid combinations.

💡 Check if n is within the range of possible sums for k numbers.

💡 For k=1, only numbers 1 to 9 are valid candidates.

💡 Return empty list if no single number equals n.

Why it failed: Returned non-empty list for impossible sum. Fix by verifying candidate numbers are within 1 to 9 and sum equals n.

✓ Correctly returns empty list when no valid single number matches n.

t2_03edge

Input{"k":9,"n":45}

Expected[[1,2,3,4,5,6,7,8,9]]

⏱ Performance - must finish in 2000ms

Sum of numbers 1 through 9 is 45, so the only combination of size 9 summing to 45 is all numbers.

💡 Sum of first 9 natural numbers is 45; check if n equals this sum when k=9.

💡 If yes, return the full list from 1 to 9 as the only combination.

💡 Avoid unnecessary recursion by checking this boundary condition.

Why it failed: Missed the full set combination for k=9 and n=45. Fix by adding a boundary check for this exact sum.

✓ Correctly returns the full set when k=9 and n=45.

t3_01corner

Input{"k":3,"n":15}

Expected[[1,5,9],[1,6,8],[2,4,9],[2,5,8],[2,6,7],[3,4,8],[3,5,7],[4,5,6]]

⏱ Performance - must finish in 2000ms

Multiple combinations of 3 numbers sum to 15; tests correct enumeration and pruning.

💡 Avoid greedy approach that picks largest numbers first; all combinations must be found.

💡 Use backtracking to explore all valid subsets of size k.

💡 Prune branches where sum exceeds n or combination size exceeds k.

Why it failed: Greedy approach missed valid combinations. Fix by exploring all branches with backtracking instead of picking largest numbers first.

✓ All valid combinations found, no greedy misses.

t3_02corner

Input{"k":2,"n":17}

Expected[[8,9]]

⏱ Performance - must finish in 2000ms

Tests that numbers are used only once; no repeated numbers allowed.

💡 Ensure each number is used at most once in a combination.

💡 Increment start index after choosing a number to avoid reuse.

💡 Check that combinations do not contain duplicates.

Why it failed: Repeated numbers in combinations detected. Fix by incrementing start index to prevent reuse of same number.

✓ No repeated numbers in any combination.

t3_03corner

Input{"k":4,"n":1}

Expected[]

⏱ Performance - must finish in 2000ms

Sum too small for k=4 numbers; no valid combinations.

💡 Minimum sum for k numbers is sum of first k natural numbers.

💡 If n is less than this minimum, return empty list immediately.

💡 Add pruning to avoid unnecessary recursion.

Why it failed: Returned non-empty list for impossible sum. Fix by adding minimum sum check: if n < k*(k+1)/2, return [].

✓ Correctly returns empty list when sum too small for k numbers.

t4_01performance

Input{"k":9,"n":45}

Expectednull

⏱ Performance - must finish in 2000ms

Maximum input size with k=9 and n=45; algorithm must complete within 2 seconds despite exponential search space.

💡 Backtracking with pruning is essential to avoid TLE.

💡 Use early stopping when sum exceeds n or combination size exceeds k.

💡 Avoid recomputation by incrementing start index and pruning impossible branches.

Why it failed: Algorithm timed out due to exponential complexity without pruning. Fix by adding pruning conditions and early stopping.

✓ Algorithm runs within time limit using pruning and backtracking.

Practice

1. Consider the following Python code for finding the largest divisible subset. What is the final returned list when the input is [1, 2, 3]?

from typing import List

def largestDivisibleSubset(nums: List[int]) -> List[int]:
    if not nums:
        return []
    nums.sort()
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    max_index = 0

    for i in range(n):
        for j in range(i - 1, -1, -1):
            if nums[i] % nums[j] == 0:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            else:
                break
        if dp[i] > dp[max_index]:
            max_index = i

    result = []
    while max_index >= 0:
        result.append(nums[max_index])
        max_index = prev[max_index]
    return result[::-1]

print(largestDivisibleSubset([1, 2, 3]))

easy

A. [1, 2]

B. [1, 3]

C. [1, 2, 3]

D. [2, 3]

Solution

1. Step 1: Trace dp and prev arrays

   Sorted nums = [1, 2, 3]. For i=1 (2), dp[1]=2, prev[1]=0 since 2 % 1 == 0. For i=2 (3), dp[2]=2, prev[2]=0 since 3 % 1 == 0 but 3 % 2 != 0 (break early).

2. Step 2: Reconstruct subset from max_index=1 or 2

   dp[1] and dp[2] both 2, max_index updated to 2 last. Reconstruct: nums[2]=3, prev[2]=0 -> nums[0]=1. Result reversed is [1, 3].

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Subset [1,3] is largest divisible subset returned [OK]

Hint: Trace dp and prev arrays carefully [OK]

Common Mistakes:

• Assuming [1,2,3] all divisible chain without checking divisibility
• Confusing indices when reconstructing subset
• Ignoring early break in inner loop

2. The following code attempts to solve the Matchsticks to Square problem using backtracking with bitmask and memoization. Identify the line containing the subtle bug that can cause incorrect results or infinite recursion.

medium

A. Line with 'if total % 4 != 0: return false' (no divisibility check)

B. Line with 'matchsticks.sort(reverse=true)' (missing sorting causes inefficiency)

C. Line with 'memo[(used_mask, curr_sum, sides_formed)] = false' (incorrect memoization)

D. Line with recursive call 'backtrack(next_mask, next_sum, sides_formed)' missing return statement

Solution

1. Step 1: Identify missing return in recursion

   The recursive call without return means the function ignores successful paths, causing incorrect results or infinite recursion.

2. Step 2: Confirm other lines are correct

   Divisibility check is present, sorting is done, and memoization line is correct for caching failures.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing return in recursive call breaks backtracking correctness [OK]

Hint: Missing return in recursive call breaks correctness [OK]

Common Mistakes:

• Forgetting to return recursive call result
• Skipping divisibility check
• Not sorting before backtracking

3. 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)

4. Suppose the problem changes: now candidates can include negative numbers, and you still want all unique combinations summing to the target with reuse allowed. Which modification to the backtracking approach is necessary to handle this variant correctly?

hard

A. Remove pruning on target < 0 and add a visited set to detect cycles to avoid infinite recursion.

B. No change needed; the existing backtracking with pruning on target < 0 still works correctly.

C. Sort candidates in descending order and prune when target is less than the smallest candidate.

D. Use dynamic programming instead of backtracking because negative numbers break recursion.

Solution

1. Step 1: Understand impact of negative candidates

   Negative numbers allow sums to decrease indefinitely, causing infinite recursion if pruning on target < 0 is used or missing.

2. Step 2: Modify pruning and cycle detection

   Pruning on target < 0 is invalid because target can oscillate; must remove it and add a visited set or memoization to detect repeated states and avoid infinite loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detection is essential when negative numbers allow infinite recursion [OK]

Hint: Negative numbers require cycle detection to prevent infinite recursion [OK]

Common Mistakes:

• Assuming pruning on target < 0 always applies
• Ignoring infinite recursion caused by negatives

5. Suppose the problem is modified so that letters can be toggled multiple times, allowing reuse of characters in permutations (e.g., toggling the same letter case multiple times in different positions). Which modification to the backtracking approach correctly handles this variant without generating duplicates?

hard

A. Use a visited set to track permutations and skip duplicates after generation

B. Modify recursion to allow toggling letters multiple times but prune branches that revisit the same index

C. Change the algorithm to generate permutations with replacement by increasing recursion depth beyond string length

D. Use iterative BFS with a queue that enqueues toggled strings and avoids revisiting states

Solution

1. Step 1: Understand reuse variant

   Allowing reuse means letters can be toggled multiple times in different positions, increasing state space and possible duplicates.

2. Step 2: Identify correct approach

   Iterative BFS with a queue can track states and avoid revisiting duplicates efficiently, unlike naive recursion which may generate duplicates or infinite loops.

3. Step 3: Why other options fail

   Visited sets after generation are inefficient; pruning recursion by index doesn't prevent reuse; increasing recursion depth breaks problem constraints.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   BFS with state tracking handles reuse and duplicates [OK]

Hint: Use BFS with visited states to handle reuse [OK]

Common Mistakes:

• Trying to prune recursion by index only
• Ignoring duplicates generated by reuse