文章 217
评论 7
浏览 146900
Backtracking - 216. Combination Sum III

Backtracking - 216. Combination Sum III

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]]

思路:

这一题是组合系列的变形题,要求用k个1-9的数组组合出n值,采用回溯来做,使用组合的个数为k个和为n来剪枝。

代码:

func combinationSum3(k int, n int) [][]int {

    var res [][]int
    dfs(1, k, n, 0, []int{}, &res)
    return res
}

func dfs(start, k, n, sum int, temp []int, res *[][]int) {
    if sum == n && k == 0 {
        *res = append(*res, append([]int{}, temp...))
        return
    }
    if k == 0 {
        return 
    }
    
    for i := start; i <= 9; i++ {
        temp = append(temp, i)
        dfs(i+1, k-1, n, sum + i, temp, res)
        temp = temp[:len(temp)-1]
    }
}

标题:Backtracking - 216. Combination Sum III
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/09/03/1567526005573.html

Nothing just happens, it's all part of a plan.

取消