216. Combination Sum III
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.
Note:
- All numbers will be positive integers.
- The solution set must not contain duplicate combinations.
Example 1:
代码语言：javascript复制Input: k = 3, n = 7
Output: [[1,2,4]]Example 2:
代码语言：javascript复制Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]思路：
这一题是组合系列的变形题，要求用k个1-9的数组组合出n值，采用回溯来做，使用组合的个数为k个和为n来剪枝。
代码：
代码语言：javascript复制func combinationSum3(k int, n int) [][]int {
var res [][]int
dfs(1, k, n, 0, []int{}, &res)
return res
}
func dfs(start, k, n, sum int, temp []int, res *[][]int) {
if sum == n && k == 0 {
*res = append(*res, append([]int{}, temp...))
return
}
if k == 0 {
return
}
for i := start; i <= 9; i {
temp = append(temp, i)
dfs(i 1, k-1, n, sum i, temp, res)
temp = temp[:len(temp)-1]
}
}
