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.
Example 4:
**Input:** k = 3, n = 2
**Output:** []
**Explanation:** There are no valid combinations.
Example 5:
**Input:** k = 9, n = 45
**Output:** [[1,2,3,4,5,6,7,8,9]]
**Explanation:**
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
There are no other valid combinations.
Constraints:
2 <= k <= 9
1 <= n <= 60
ac
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
// DFS, backtracking
List<List<Integer>> res = new ArrayList<List<Integer>>();
// edge cases
if (k < 1 || n < 1) return res;
// DFS
backtrack(1, k, n, new ArrayList<Integer>(), res);
return res;
}
private void backtrack(int s, int k, int remain, List<Integer> note, List<List<Integer>> res) {
// walk, s <= i <= 9
// if k == 1, stop, check remain. if remain == 0, add. remain < 0 continue, >0 return.
// if k > 1 recursion -> if remain <= 0, return.
// exit
if (s > 9 || k < 1 || remain < 0) return;
// last one
if (k == 1) {
for (int i = s; i <= 9; i++) {
if (i < remain) {
continue;
} else if (i == remain) {
note.add(i);
res.add(new ArrayList<Integer>(note));
note.remove(note.size()-1);
return;
} else if (i > remain){
return;
}
}
return;
}
// k > 1, continue recursion
for (int i = s; i <= 9; i++) {
if (i >= remain) return;
note.add(i);
backtrack(i+1, k-1, remain-i, note, res);
note.remove(note.size()-1);
}
}
}
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
backtrack(1, k, n, res, new ArrayList<Integer>());
return res;
}
private void backtrack(int start, int remainK, int remainN, List<List<Integer>> res, List<Integer> note) {
if (remainK == 0) { // up to k numbers
if (remainN == 0) { // add up to number n
res.add(new ArrayList<Integer>(note));
}
return;
}
for (int i = start; i <= 9; i++) {
note.add(i);
backtrack(i+1, remainK-1, remainN - i, res, note);
note.remove(note.size()-1);
}
}
}