求和为target的所有组合
题目
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，
并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
解析
涉及到排列组合问题，或者说求多个解的问题，都优先考虑DFS。套用DFS公式：
找到递归边界：组合之和大于等于target，或者最新加入组合的元素大于等于target-sum(当前组合)再找到状态遍历：for range candidates，搜索树的每个节点都可以选取所有元素然后看如何递归进行状态转移，在这里由于每次搜索都增加一个元素，只要递归调用中更新当前组合就行，递归调用里基于入参往组合里添加元素- 最后
考虑回溯，即当达到递归边界时，递归调用返回，当前分支搜索结束，进行下一个分支搜索，需要将调用递归前往当前组合中添加进来的元素剔除掉
实现
//用于获取所有组合
var targetFrom = make([][]int, 0)
//用于去重
var alreadyMap = make(map[string]struct{})
func getTargetBy(candidates []int, childSet []int, target int) bool {
sum := intSum(childSet)
//终止条件
if sum >= target {
if sum == target {
return true
}
return false
}
length := len(candidates)
for i := 0; i < length; i ++ {
childSet = append(childSet, candidates[i])
if getTargetBy(candidates, childSet, target) {
tmpSet := make([]int, len(childSet))
copy(tmpSet, childSet)
key := getKey(tmpSet)
if _, ok := alreadyMap[key]; !ok {
targetFrom = append(targetFrom, tmpSet)
alreadyMap[key] = struct{}{}
}
}
//回溯
childSet = childSet[:len(childSet)-1]
}
return false
}
func intSum(arr []int) int {
sum := 0
for _,v := range arr {
sum += v
}
return sum
}
func getKey(arr []int) string {
sort.Slice(arr, func(i, j int) bool {
return arr[i] < arr[j]
})
key := ""
for i,v := range arr {
subKey := fmt.Sprintf("%v", v)
if i == 0 {
key = subKey
} else {
key += fmt.Sprintf("-%s", subKey)
}
}
return key
}