Combination Sum
描述
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
* All numbers (including target) will be positive integers.
* The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]
题解
package algrithms
import "sort"
func combinationSum(candidates []int, target int) [][]int {
sort.Ints(candidates)
var helper func(candidate, share []int, target int)
var r [][]int
helper = func(c, share []int, target int) {
if target == 0 {
r = append(r, share)
return
}
if len(c) == 0 || target < c[0] {
return
}
share = share[:len(share):len(share)]
helper(c, append(share, c[0]), target-c[0])
helper(c[1:], share, target)
}
helper(candidates, []int{}, target)
return r
}