39. 组合总和

题目描述：

给你一个 无重复元素 的整数数组 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 <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

---

解题分析及思路：

方法：回溯

思路：

1. 定义递归函数： 定义一个递归函数 dfs，该函数用于在当前选择的基础上继续搜索可能的组合。参数包括当前搜索起始位置 index、剩余需要凑成的目标值 sub，以及当前已选择的组合 res。
2. 递归搜索： 在 dfs 函数中，使用循环遍历候选数组 candidates，从给定的 index 开始。对于每个候选数字 candidates[i]，如果剩余目标值 sub - candidates[i] 大于等于 0，说明可以选择当前数字，将其加入到当前组合 res 中，并递归调用 dfs 函数继续搜索下一个数字。
3. 回溯操作： 在递归调用返回后，需要将刚加入的数字从当前组合 res 中移除，以便尝试其他可能的数字组合。
4. 结束条件： 如果剩余需要凑成的目标值 sub 等于 0，表示已经成功凑成目标，将当前组合 res 加入到结果集中。
5. 返回结果： 最终将所有找到的组合存储在结果集 result 中，并在递归结束后返回结果集。

func combinationSum(candidates []int, target int) (result [][]int) {
	var dfs func(index, sub int, res []int)
	dfs = func(index, sub int, res []int) {
		if sub == 0 {
			result = append(result, append([]int{}, res...))
			return
		}
		for i := index; i < len(candidates); i++ {
			if sub-candidates[i] >= 0 {
				res = append(res, candidates[i])
				dfs(i, sub-candidates[i], res)
				res = res[:len(res)-1]
			}
		}
	}
	dfs(0, target, []int{})
	return result
}

复杂度：

• 时间复杂度：O(O(2^n * n))
• 空间复杂度：O(N)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:2.8 MB,击败了36.79% 的Go用户