leetcode——组合总和（回溯算法详细讲解）

在面试或刷题过程中，回溯算法是一个绕不开的核心算法之一。今天，我们来详细解析 LeetCode 39「组合总和」 问题，并用 Java 回溯 + 剪枝优化 来高效解决它！这篇文章不仅适合初学者，也适合希望提高回溯算法的朋友们。

给你一个 无重复元素 的整数数组 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.经过分析，我们可以使用回溯中的选或者不选方法来进行解题。

2.首先，到达边界条件时，且我们的left为零的时候，也就是我们达到了目标值，将列表path添加进ans中。

3.如果到达了边界，且left不为零时，或者left小于零时，直接返回即可。

4.不选，直接进入下一步的递归。

5.选，直接将当前元素添加进path中，然后进入下一步的递归即可。

6.最后，我们要将path最后一个元素删除恢复现场，达到回溯的效果。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, target, candidates, ans, path);
        return ans;
    }
    private void dfs(int i, int left, int[] candidates, List<List<Integer>> ans, List<Integer> path) {
        if (left == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        if (i == candidates.length || left < 0) {
            return;
        }
        dfs(i + 1, left, candidates, ans, path);
        path.add(candidates[i]);
        dfs(i, left - candidates[i], candidates, ans, path);
        path.remove(path.size() - 1);
    }
}

时间复杂度分析

时间复杂度分析：
由于回溯算法会遍历所有可能的组合，最坏情况下的时间复杂度大约为 O(2^N)，但由于剪枝优化，实际运行效率要高于暴力搜索。
空间复杂度： 主要由递归栈深度决定，为 O(target / min(candidates))。

 总结与延伸

 思考：如果 candidates 里有重复元素，该如何去重？
扩展：这道题和「零钱兑换」问题（动态规划解法）有何不同？