039.md

Combination Sum

题目:

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.

Example 1:

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

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

思路：

    回溯法。
    比如例子2:
	尝试的过程为:
	[] target = 8
	[2] target = 6
	[2,2] target = 4
	[2,2,2] target = 6
	[2,2,2,2] target = 8 满足条件记录下来，回溯到上一步
	[2,2,2,3] target = -1 target < 0 回溯
	[2,2,2,5] target = -3 target < 0 回溯
	[2,2,2] 遍历完毕 回溯
	[2,2,3] target = 1 
	[2,2,3,3] target = -2 target < 0 回溯
	[2,2,3,5] target = -4 target < 0 回溯
	[2,2,3] 遍历完毕 回溯
	[2,3] target = 5
	[2,3,3] target = 8 满足条件记录下来，回溯
	.....

代码：

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

func backtrack(candidates []int,target int,chosen []int, res *[][]int, begin int) bool {
    if target < 0 {
        return false
    }
    if target == 0 {
        one_res := make([]int, len(chosen))
        copy(one_res, chosen)
        *res = append(*res, one_res)
        return false
    }
    for i := begin; i < len(candidates); i += 1 {
        if !backtrack(candidates, target-candidates[i], append(chosen, candidates[i]), res, i) {
            break
        }
    }
    return true
    
}