Backtracking - 216. Combination Sum III

    leetcode backtracking
    60

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