给你一个 无重复元素 的整数数组
candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为
target的不同组合数少于150个。示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
提示：
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
思路：
参考 B站视频题解，从下标i=0开始不断尝试添加新元素，通过回溯搜索最终找到满足要求的方案。
时间复杂度：见 LeetCode官方题解
空间复杂度：
O(target)。除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 O(target) 层。
// 版本1 累加sum，用于与target做比较// var res [][]int// func combinationSum(candidates []int, target int) [][]int {// dfs(candidates, target, []int{}, 0)// return res// }// func dfs(candidates []int, target int, arr []int, sum int) {// if sum > target {// return// }// if sum == target {// tmpArr := make([]int, len(arr))// copy(tmpArr, arr)// res = append(res, tmpArr)// return// }// // sum < target// for i := 0; i < len(candidates); i++ {// arr = append(arr, candidates[i])// 追加// dfs(candidates, target, arr, sum + candidates[i])// arr = arr[:len(arr)-1] // 回溯// }// }// 版本2：累加sum，用于与target做比较// 版本1会把不同顺序的选取方式作为不同的方案，所以此时需要去掉重复的情况，dfs()中另加index参数// 思路：从下标i=0开始不断尝试添加新元素，通过回溯搜索最终找到满足要求的方案。// 参考 B站视频：https://www.bilibili.com/video/BV1h14y1A7yR/?spm_id_from=333.337.search-card.all.click&vd_source=2c268e25ffa1022b703ae0349e3659e4// var res [][]int// func combinationSum(candidates []int, target int) [][]int {// res = make([][]int, 0) // 一定要加这一行，初始化res，否则不同用例在跑的时候 res会被覆盖导致 res值为上次的值// dfs(candidates, target, []int{}, 0, 0)// return res// }// func dfs(candidates []int, target int, arr []int, sum, index int) {// if sum > target {// return// }// if sum == target {// tmpArr := make([]int, len(arr))// copy(tmpArr, arr)// res = append(res, tmpArr)// return// }// // sum < target// // 避免每次遍历candidates时从i=0开始，导致结果重复，比如2,2,3和2,3,2 !!!// for i := index; i < len(candidates); i++ {// arr = append(arr, candidates[i])// 追加// dfs(candidates, target, arr, sum + candidates[i], i)// arr = arr[:len(arr)-1] // 回溯// }// }// 版本3：去除sum参数，仅利用target每次递减即可varres [][]intfunccombinationSum(candidates []int, targetint) [][]int { res=make([][]int, 0) dfs(candidates, target, 0, []int{}) returnres} funcdfs(candidates []int, target, indexint, arr []int) { iftarget==0 { tmp :=make([]int, len(arr)) copy(tmp, arr) res=append(res, tmp) return } elseiftarget<0 { return } fori :=index; i<len(candidates); i++ { arr=append(arr, candidates[i]) // 因为同一个 数字可以 无限制重复被选取，所以第三个参数传入i而不是i+1dfs(candidates, target-candidates[i], i, arr) arr=arr[:len(arr) -1] } } // 版本4 动态规划的思想// 参考 B站视频：https://www.bilibili.com/video/BV1h14y1A7yR/?spm_id_from=333.337.search-card.all.click&vd_source=2c268e25ffa1022b703ae0349e3659e4
