题目：216. 组合总和 III

🚀 本题 LeetCode 传送门

题目大意

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

说明：

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

解题思路

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

代码

  1. package leetcode
  3. func combinationSum3(k int, n int) [][]int {
  4.  if k == 0 {
  5.   return [][]int{}
  6.  }
  7.  c, res := []int{}, [][]int{}
  8.  findcombinationSum3(k, n, 1, c, &res)
  9.  return res
  10. }
  12. func findcombinationSum3(k, target, index int, c []int, res *[][]int) {
  13.  if target == 0 {
  14.   if len(c) == k {
  15.    b := make([]int, len(c))
  16.    copy(b, c)
  17.    *res = append(*res, b)
  18.   }
  19.   return
  20.  }
  21.  for i := index; i < 10; i++ {
  22.   if target >= i {
  23.    c = append(c, i)
  24.    findcombinationSum3(k, target-i, i+1, c, res)
  25.    c = c[:len(c)-1]
  26.   }
  27.  }
  28. }