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. You are given a string containing letters and digits. You need to generate all possible strings by toggling the case of each letter independently, while digits remain unchanged. Which algorithmic approach guarantees generating all valid permutations efficiently?

easy

A. Backtracking with include/exclude choices for each letter's case

B. Sorting the string and then generating permutations by swapping adjacent characters

C. Dynamic programming using a bottom-up table to store partial permutations

D. Greedy algorithm that toggles letters only when it reduces the lexicographical order

Solution

1. Step 1: Understand problem constraints

   The problem requires exploring all combinations of letter cases, which is a classic subsets problem where each letter can be included as lowercase or uppercase.

2. Step 2: Identify suitable algorithm

   Backtracking with include/exclude choices for each letter's case systematically explores all 2^k combinations, ensuring completeness and correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores all subsets of letter cases [OK]

Hint: Toggle letter cases via backtracking subsets [OK]

Common Mistakes:

• Thinking greedy can find all permutations
• Using DP that doesn't fit subsets pattern

2. Consider the following Python code implementing the optimal backtracking with bitmask and memoization approach for the Matchsticks to Square problem. Given the input [1,1,2,2,2], what is the final return value of makesquare([1,1,2,2,2])?

easy

A. True

B. Depends on the order of matchsticks

C. Raises an exception due to index error

D. False

Solution

1. Step 1: Calculate total and side length

   Total = 1+1+2+2+2 = 8, side = 8/4 = 2.

2. Step 2: Trace backtracking calls

   Sorted sticks: [2,2,2,1,1]. The algorithm tries to form sides of length 2. It can form three sides with three 2's, and the last side with two 1's. Hence, returns true.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum divisible by 4 and sticks fit sides exactly [OK]

Hint: Sum divisible by 4 and sticks fit sides exactly [OK]

Common Mistakes:

• Forgetting to sort and prune
• Assuming order affects result
• Miscounting sides formed

3. You are given an array of positive integers and a number k. The task is to determine if the array can be partitioned into k subsets such that the sum of elements in each subset is equal. Which algorithmic approach guarantees an optimal solution for this problem?

easy

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

B. Greedy algorithm that picks the largest elements first and assigns them to subsets

C. Backtracking with bitmask memoization to explore subsets and prune invalid states

D. Sorting and then using a sliding window to find equal sum partitions

Solution

1. Step 1: Understand problem constraints and complexity

   The problem requires partitioning into exactly k subsets with equal sums, which is NP-complete and requires exploring combinations exhaustively.

2. Step 2: Evaluate algorithm suitability

   Greedy and sliding window approaches fail to guarantee correctness because they don't explore all combinations. Simple DP without pruning is inefficient and incomplete. Backtracking with bitmask memoization efficiently prunes and caches states, guaranteeing optimality.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Backtracking with memoization handles all subsets optimally [OK]

Hint: Bitmask memoization prunes repeated subset states [OK]

Common Mistakes:

• Assuming greedy always works for equal sum partition
• Confusing subset sum DP with partitioning into k subsets

4. Suppose the problem is changed so that candidates can be reused unlimited times (unlike original no reuse). Which modification to the backtracking algorithm correctly adapts to this change?

hard

A. Change recursive call from backtrack(i + 1, ...) to backtrack(i, ...) to allow reuse of the same candidate

B. Keep backtrack(i + 1, ...) but remove duplicate skipping to allow repeated combinations

C. Add a global visited set to prevent reusing candidates in the same combination

D. Sort candidates and prune only when candidate >= target, but keep recursion unchanged

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means the same candidate index can be chosen multiple times in the same combination.

2. Step 2: Modify recursion call

   Changing recursive call from backtrack(i + 1, ...) to backtrack(i, ...) allows the same candidate to be reused multiple times.

3. Step 3: Keep duplicate skipping and pruning as before

   Duplicate skipping still applies to avoid repeated combinations, and pruning remains to optimize.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Recurse with same index to allow reuse [OK]

Hint: Reuse means recurse with same index, not next index [OK]

Common Mistakes:

• Removing duplicate skipping causes duplicates
• Using visited set breaks reuse logic
• Pruning incorrectly changes conditions

5. Suppose the problem is modified so that elements can be reused multiple times in the subset (i.e., the subset can contain duplicates). Which modification to the algorithm is necessary to correctly find the largest divisible subset under this new constraint?

hard

A. Modify DP to consider all previous elements including i itself, allowing repeated use, and remove early break

B. Switch to a graph cycle detection algorithm to handle repeated elements

C. Use the same DP approach but allow dp[i] to consider dp[i] itself for reuse, enabling cycles

D. Use a greedy approach picking the largest element repeatedly until no more divisible

Solution

1. Step 1: Understand reuse impact

   Allowing reuse means elements can appear multiple times, so dp must consider extending from the same element multiple times.

2. Step 2: Modify DP logic

   DP inner loop must consider j ≤ i (including i itself) and remove early break because sorted order no longer guarantees divisibility breaks.

3. Step 3: Reject incorrect options

   Greedy fails to find longest chain; graph cycle detection is unnecessary; naive DP without modification misses reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP adjusted for reuse and no early break handles duplicates [OK]

Hint: Reuse requires DP to consider self and no early break [OK]

Common Mistakes:

• Using original DP without changes leads to incorrect results
• Trying greedy approach which fails on complex divisibility
• Confusing graph cycles with DP chains