题目

给你一个 无重复元素 的整数数组 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
}