leetcode 216 组合总和iii_谜底666的博客-爱代码爱编程

题目

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9 每个数字
• 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

解析

这道题和上一道组合问题很接近，只不过是多了一个终止条件，直接上回溯+剪枝的代码：

func combinationSum3(k int, n int) [][]int {
    //要找K个数的和为n
    var res [][]int
    var path []int
    sum := 0
    var backTrack func(int)
    backTrack = func(startIndex int) {
        //剪枝
        if sum > n || len(path) > k {
            return 
        }
        //递归终止条件
        if len(path) == k && sum == n {
            tmp := make([]int, k) //一样的原因
            copy(tmp, path)
            res = append(res, tmp)
            return
        }
        //单层递归循环+剪枝
        for i := startIndex; i <= 9-(k-len(path))+1; i++ {
            sum += i
            path = append(path, i)
            backTrack(i+1)
            //回溯
            sum -= i
            path = path[:len(path)-1]
        }
    }
    backTrack(1)
    return res
}

也可以将结果定义成函数外面的全局变量，然后在外定义函数；或者传数组的地址进来：

func combinationSum3(k int, n int) [][]int {
    //要找K个数的和为n
    var res [][]int
    var path []int
    var sum int
    backTrack(n, k, 1, sum, &path, &res)
    return res
}

func backTrack(n, k, startIndex, sum int, path *[]int, res *[][]int) {
    if sum > n || len(*path) > k {
        return
    }
    if sum == n && len(*path) == k {
        tmp := make([]int, k)
        copy(tmp, *path)
        *res = append(*res, tmp)
        return
    }
    for i := startIndex; i <= 9-(k-len(*path))+1; i++ {
        sum += i
        *path = append(*path, i)
        backTrack(n, k, i+1, sum, path, res)
        sum -= i
        *path = (*path)[:len(*path)-1]
    }
}