216. 组合总和 III

组合总和 III

• 难度: medium
• 原始链接: https://leetcode.cn/problems/combination-sum-iii
• 标签: 回溯

解法一: 回溯

go

func combinationSum3(k int, n int) [][]int {
  ans := [][]int{}
  var dfs func(cur, sum int, list []int)
  dfs = func(cur, sum int, list []int) {
    if len(list) == k && sum == n {
      newList := make([]int, k)
      copy(newList, list)
      ans = append(ans, newList)
      return
    }
    if cur > 9 || len(list) > k || sum > n {
      return
    }
    for i := cur; i <= 9; i++ {
      list = append(list, i)
      sum += i
      dfs(i+1, sum, list)
      sum -= i
      list = list[:len(list)-1]
    }
  }
  dfs(1, 0, []int{})
  return ans
}