Combination Sum III

LeetCode 216 | Difficulty: Medium

Medium

Problem Description

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

- Only numbers `1` through `9` are used.

- Each number is used **at most once**.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Constraints:

- `2 <= k <= 9`

- `1 <= n <= 60`

Topics: Array, Backtracking

---

Approach

Backtracking

Explore all candidates by building solutions incrementally. At each step, choose an option, explore further, then unchoose (backtrack) to try the next option. Prune branches that can't lead to valid solutions.

When to use

Generate all combinations/permutations, or find solutions that satisfy constraints.

---

Solutions

Solution 1: C# (Best: 288 ms)

Metric	Value
Runtime	288 ms
Memory	N/A
Date	2018-03-01

Solution

public class Solution {
    public IList<IList<int>> CombinationSum3(int k, int n) {
      List<IList<int>> dp = new List<IList<int>>();
    int[] candidates = Enumerable.Range(1,9).ToArray();
    bool[] used = new bool[9];
    backtrack(dp, new List<int>(), candidates,used, n,0, k);
    return dp;
}


public void backtrack(List<IList<int>> list, List<int> templist, int[] candidates, bool[] used, int target, int start, int remaining)
{
    if (remaining==0)
    {
        if(target==0) list.Add(templist.ToList());
    }
    else
    {
        for (int i = start; i < candidates.Length; i++)
        {
            if(used[i]) continue;
            templist.Add(candidates[i]);
            //templist.Dump("before backtracking");
            //Console.WriteLine($"{target - candidates[i]}, start: {i}");
            used[i] = true;
            backtrack(list, templist, candidates, used, target - candidates[i],i+1, remaining-1);
            used[i] = false;
            templist.RemoveAt(templist.Count - 1);
            //templist.Dump("after removing");
        }
    }

}
}

---

Complexity Analysis

Approach	Time	Space
Backtracking	$O(n! or 2^n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Identify pruning conditions early to avoid exploring invalid branches.