Leetcode 39

[zwwhdls]

求数组里的数相加等于给定值的组合

题意

给定一个不重复的数组，每个数可以重复使用，找出所有可能的组合相加等于给定值。

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

思路: DFS

代码:

func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    result := make([][]int, 0)
    dfs(candidates, target, 0, []int{}, &result)
    return result
}

func dfs(candidates []int, target int, sum int, nums []int, result *[][]int) {
    for i, candidate := range candidates {

        if sum+candidate == target {
            resTemp := make([]int, len(nums) + 1)
            copy(resTemp, append(nums, candidate))

            *result = append(*result, resTemp)
        }
        if sum+candidate < target {
            //nums = append(nums, candidate)
            dfs(candidates[i:], target, sum+candidate, append(nums, candidate), result)
        } else {
            break
        }

    }
}