0216. Combination Sum I I I

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

``````Input: k = 3, n = 7
Output: [[1,2,4]]
``````

Example 2:

``````Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]
``````

• 所有数字都是正整数。
• 解集不能包含重复的组合。

## 解题思路 #

• 这一题比第 39 题还要简单一些，在第 39 题上稍加改动就可以解出这一道题。
• 第 39 题是给出数组，这一道题数组是固定死的 [1,2,3,4,5,6,7,8,9]，并且数字不能重复使用。

## 代码 #

``````
package leetcode

func combinationSum3(k int, n int) [][]int {
if k == 0 {
return [][]int{}
}
c, res := []int{}, [][]int{}
findcombinationSum3(k, n, 1, c, &res)
return res
}

func findcombinationSum3(k, target, index int, c []int, res *[][]int) {
if target == 0 {
if len(c) == k {
b := make([]int, len(c))
copy(b, c)
*res = append(*res, b)
}
return
}
for i := index; i < 10; i++ {
if target >= i {
c = append(c, i)
findcombinationSum3(k, target-i, i+1, c, res)
c = c[:len(c)-1]
}
}
}

``````

Sep 6, 2020