# 216. Combination Sum III

## 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

## Solutions

DFS.

This is a typical backtracking problem that explores all possible combinations to find those that meet the criteria.

### Function Signature

def combinationSum3(self, k: int, n: int) -> List[List[int]]:

• The function combinationSum3 takes two arguments: k, the number of digits in each combination, and n, the target sum.
• It returns a list of lists, where each inner list is a combination of k digits that add up to n.

### The dfs (Depth-First Search) Helper Function

def dfs(start, s, t): # s: sum, t: list

• dfs is a recursive helper function defined within combinationSum3. It is used to perform a depth-first search to explore all possible combinations.
• start: The starting point for the current exploration, ensuring that only numbers greater than start are considered to avoid repeats and maintain uniqueness.
• s: The current sum of the numbers in the temporary list t.
• t: A temporary list that stores the current combination being explored.

### The Recursive Exploration

• The recursion starts with dfs(1, 0, []), meaning the search begins with the number 1, the current sum as 0, and an empty list for the combination.
• The base case of the recursion checks if the current sum s exceeds n or if the length of the temporary list t exceeds k. If either condition is true, the recursion returns, as the current path cannot yield a valid combination.
• Another base case checks if s == n and len(t) == k. If both conditions are met, a valid combination is found, and a copy of t is added to the answer list ans. The copy is used because t is modified in subsequent steps.
• The recursive step iterates from start to 9 (inclusive of 1 and exclusive of 10 because we’re dealing with digits). For each number i in this range, it is added to t, and dfs is called recursively with the updated parameters: the next starting number (i + 1), the new sum (s + i), and the updated temporary list t. After the recursive call returns, t.pop() is called to backtrack, removing the last number added to t and exploring other possibilities.

### Collecting and Returning the Answer

• ans is initialized as an empty list. It collects all valid combinations found during the depth-first search.
• After exploring all possibilities through recursive backtracking, ans is returned, containing all combinations of k numbers that sum to n.
• class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int k;

public List<List<Integer>> combinationSum3(int k, int n) {
this.k = k;
dfs(1, n);
return ans;
}

private void dfs(int i, int s) {
if (s == 0) {
if (t.size() == k) {
}
return;
}
if (i > 9 || i > s || t.size() >= k) {
return;
}
dfs(i + 1, s - i);
t.remove(t.size() - 1);
dfs(i + 1, s);
}
}

• class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> ans;
vector<int> t;
function<void(int, int)> dfs = [&](int i, int s) {
if (s == 0) {
if (t.size() == k) {
ans.emplace_back(t);
}
return;
}
if (i > 9 || i > s || t.size() >= k) {
return;
}
t.emplace_back(i);
dfs(i + 1, s - i);
t.pop_back();
dfs(i + 1, s);
};
dfs(1, n);
return ans;
}
};

• class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def dfs(start, s, t): # s: sum, t: list
if s > n or len(t) > k:
return
if s == n and len(t) == k:
ans.append(t.copy())
return

for i in range(start, 10):
t.append(i)
dfs(i + 1, s + i, t)
t.pop()

ans = []
dfs(1, 0, [])
return ans


• func combinationSum3(k int, n int) (ans [][]int) {
t := []int{}
var dfs func(i, s int)
dfs = func(i, s int) {
if s == 0 {
if len(t) == k {
ans = append(ans, slices.Clone(t))
}
return
}
if i > 9 || i > s || len(t) >= k {
return
}
t = append(t, i)
dfs(i+1, s-i)
t = t[:len(t)-1]
dfs(i+1, s)
}
dfs(1, n)
return
}

• function combinationSum3(k: number, n: number): number[][] {
const ans: number[][] = [];
const t: number[] = [];
const dfs = (i: number, s: number) => {
if (s === 0) {
if (t.length === k) {
ans.push(t.slice());
}
return;
}
if (i > 9 || i > s || t.length > k) {
return;
}
t.push(i);
dfs(i + 1, s - i);
t.pop();
dfs(i + 1, s);
};
dfs(1, n);
return ans;
}


• public class Solution {
private List<IList<int>> ans = new List<IList<int>>();
private List<int> t = new List<int>();
private int k;

public IList<IList<int>> CombinationSum3(int k, int n) {
this.k = k;
dfs(1, n);
return ans;
}

private void dfs(int i, int s) {
if (s == 0) {
if (t.Count == k) {
}
return;
}
if (i > 9 || i > s || t.Count >= k) {
return;
}
dfs(i + 1, s - i);
t.RemoveAt(t.Count - 1);
dfs(i + 1, s);
}
}

• impl Solution {
pub fn combination_sum3(k: i32, n: i32) -> Vec<Vec<i32>> {
let mut ret = Vec::new();
let mut candidates = (1..=9).collect();
let mut cur_vec = Vec::new();
Self::dfs(n, k, 0, 0, &mut cur_vec, &mut candidates, &mut ret);
ret
}

fn dfs(
target: i32,
length: i32,
cur_index: usize,
cur_sum: i32,
cur_vec: &mut Vec<i32>,
candidates: &Vec<i32>,
ans: &mut Vec<Vec<i32>>
) {
if cur_sum > target || cur_vec.len() > (length as usize) {
return;
}
if cur_sum == target && cur_vec.len() == (length as usize) {
ans.push(cur_vec.clone());
return;
}
for i in cur_index..candidates.len() {
cur_vec.push(candidates[i]);
Self::dfs(target, length, i + 1, cur_sum + candidates[i], cur_vec, candidates, ans);
cur_vec.pop().unwrap();
}
}
}


• function combinationSum3(k, n) {
const ans = [];
const t = [];
const dfs = (i, s) => {
if (s === 0) {
if (t.length === k) {
ans.push(t.slice());
}
return;
}
if (i > 9 || i > s || t.length >= k) {
return;
}
t.push(i);
dfs(i + 1, s - i);
t.pop();
dfs(i + 1, s);
};
dfs(1, n);
return ans;
}