Combination Sum III
Medium · Backtracking · Explanation and code example
Backtracking over Distinct Digits
How it works
Choose increasing digits from one through nine. Increasing the next starting digit prevents reuse and duplicate orderings. Track how many digits remain and how much of the target sum remains, accepting only when both reach zero together.
Steps
- Try digits from the current start through nine.
- Recurse with one fewer slot, a smaller sum, and the next start.
- Save a path only when both remaining count and sum are zero.
Complexity
- Time: O(k × 2^9) as a conservative bound for exploring digit subsets and copying paths.
- Space: O(k) stack/path work, excluding output.
Things to watch for
- A correct sum with the wrong number of digits is invalid.
- Each digit may appear once.
- Use increasing choices so different permutations are not counted separately.
Python code example
class Solution:
def combinationSum3(self, k: int, n: int) -> list[list[int]]:
result, path = [], []
def dfs(slots, remaining, start):
if slots == 0 and remaining == 0:
result.append(path.copy())
return
if slots == 0 or remaining <= 0:
return
for value in range(start, 10):
path.append(value)
dfs(slots - 1, remaining - value, value + 1)
path.pop()
dfs(k, n, 1)
return result
C++ code example
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> ans;
dfs(k, n, 1, {}, ans);
return ans;
}
private:
void dfs(int k, int n, int s, vector<int>&& path, vector<vector<int>>& ans) {
if (k == 0 && n == 0) {
ans.push_back(path);
return;
}
if (k == 0 || n <= 0)
return;
for (int i = s; i <= 9; ++i) {
path.push_back(i);
dfs(k - 1, n - i, i + 1, std::move(path), ans);
path.pop_back();
}
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.