216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：

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


输入: _k = 3, n_ = 9
输出:** [[1,2,6], [1,3,5], [2,3,4]]

我们再来强化一下应该如何快速判断一道题是否应该使用 DFS + 回溯算法来爆搜。
总的来说，你可以从两个方面来考虑：

  • 1. 求的是所有的方案，而不是方案数。 由于求的是所有方案，不可能有什么特别的优化，我们只能进行枚举。这时候可能的解法有动态规划、记忆化搜索、DFS + 回溯算法。
  • 2. 通常数据范围不会太大，只有几十。 如果是动态规划或是记忆化搜索的题的话，由于它们的特点在于低重复/不重复枚举，所以一般数据范围可以出到 10^5105 到 10^7107，而 DFS + 回溯的话，通常会限制在 30 以内。

这道题数据范围是 30 以内，而且是求所有方案。因此我们使用 DFS + 回溯来求解：

  • 时间复杂度： DFS 回溯算法通常是指数级别的复杂度（因此数据范围通常为 30 以内）。这里暂定 O(n * 2^n)

  • 空间复杂度：同上。复杂度为 O(n * 2^n) ```go // func combinationSum3(k int, n int) [][]int { res := [][]int{}

    var dfs func(start int, temp []int, sum int) dfs = func(start int, temp []int, sum int) {

    1.   if len(temp) == k {                            //开始回溯の条件，稍有不同
    2.       if sum == n {
    3.           newTmp := make([]int, len(temp))
    4.           copy(newTmp, temp)
    5.           res = append(res, newTmp)
    6.       }
    7.       return
    8.   }
    10.   for i := start; i <= 9; i++ {                //不是数组，而是直接的整数
    11.       temp = append(temp, i)
    12.       dfs(i+1, temp, sum+i)                    //i+1开始，
    13.       temp = temp[:len(temp)-1]
    14.   }

    }

    dfs(1, []int{}, 0) return res }

```