题目描述给你一个无重复元素的整数数组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输出:[]解题思路方法一回溯 剪枝核心思路把问题看成树形结构每一层选择一个数字可以重复选同一个数字当和等于target时收集结果当和大于target时剪枝关键如何避免重复组合用start参数控制选择范围每次递归时从start开始遍历选了candidates[i]后下一层从i开始允许重复选当前数字但不能选i之前的数字避免重复组合具体过程示例candidates [2,3,6,7], target 7[] / / \ \ 2 3 6 7 /|\ |\ | 2 3 6 3 6 6 /|\ | | 2 3 6 3 6 6 | 2(和87剪枝) 有效路径: 2→2→3 (和7) ✅ 7 (和7) ✅代码实现class Solution { public: vectorvectorint combinationSum(vectorint candidates, int target) { vectorvectorint result; vectorint path; backtrack(candidates, target, 0, path, result); return result; } private: void backtrack(vectorint candidates, int target, int start, vectorint path, vectorvectorint result) { // 终止条件和等于 target if (target 0) { result.push_back(path); return; } // 剪枝和小于 0直接返回 if (target 0) return; // 从 start 开始遍历避免重复组合 for (int i start; i candidates.size(); i) { path.push_back(candidates[i]); // 选择 backtrack(candidates, target - candidates[i], i, path, result); // 递归注意传 i 而不是 i1 path.pop_back(); // 撤销 } } };复杂度分析设n是候选数组长度target是目标和。维度复杂度说明时间复杂度O(n^(target/min)))最坏情况每个位置可以选 n 个数字空间复杂度O(target/min)递归栈深度 path 长度更精确时间复杂度与解的数量和递归深度有关最坏情况为指数级。关键细节1. 为什么递归时传i而不是i1传i允许重复选当前数字如[2,2,3]传i1不允许重复选如 40 题「组合总和 II」这是本题和 40 题的核心区别。2. 为什么用start参数start控制当前层从哪个位置开始遍历避免产生重复组合。例子candidates [2,3],target 5如果不用start[2,3]和[3,2]都会出现重复用start选了 2 后下一层只能从 2 开始含 2不能选 3 之前的3. 为什么target 0要返回因为和已经超过target继续加只会更大直接剪枝。4. 排序优化可选如果先对candidates排序可以在target candidates[i]时提前breaksort(candidates.begin(), candidates.end()); // ... for (int i start; i candidates.size(); i) { if (target candidates[i]) break; // 后面的更大直接结束 // ... }方法二动态规划完全背包代码实现class Solution { public: vectorvectorint combinationSum(vectorint candidates, int target) { vectorvectorvectorint dp(target 1); dp[0] {{}}; for (int c : candidates) { for (int j c; j target; j) { for (auto comb : dp[j - c]) { vectorint newComb comb; newComb.push_back(c); dp[j].push_back(newComb); } } } return dp[target]; } };复杂度时间 O(n × target × 解的数量)空间 O(target × 解的数量)缺点需要存储所有中间结果空间大。两种方法对比方法时间复杂度空间复杂度推荐度回溯 剪枝指数级O(target/min)⭐⭐⭐⭐⭐动态规划O(n × target × 解的数量)O(target × 解的数量)⭐⭐⭐总结要点说明核心思想回溯从 start 开始遍历可以重复选当前数字关键条件递归时传i允许重复用start避免重复组合终止条件target 0收集结果target 0剪枝时间复杂度指数级空间复杂度O(target/min)
【回溯-3】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输出:[]解题思路方法一回溯 剪枝核心思路把问题看成树形结构每一层选择一个数字可以重复选同一个数字当和等于target时收集结果当和大于target时剪枝关键如何避免重复组合用start参数控制选择范围每次递归时从start开始遍历选了candidates[i]后下一层从i开始允许重复选当前数字但不能选i之前的数字避免重复组合具体过程示例candidates [2,3,6,7], target 7[] / / \ \ 2 3 6 7 /|\ |\ | 2 3 6 3 6 6 /|\ | | 2 3 6 3 6 6 | 2(和87剪枝) 有效路径: 2→2→3 (和7) ✅ 7 (和7) ✅代码实现class Solution { public: vectorvectorint combinationSum(vectorint candidates, int target) { vectorvectorint result; vectorint path; backtrack(candidates, target, 0, path, result); return result; } private: void backtrack(vectorint candidates, int target, int start, vectorint path, vectorvectorint result) { // 终止条件和等于 target if (target 0) { result.push_back(path); return; } // 剪枝和小于 0直接返回 if (target 0) return; // 从 start 开始遍历避免重复组合 for (int i start; i candidates.size(); i) { path.push_back(candidates[i]); // 选择 backtrack(candidates, target - candidates[i], i, path, result); // 递归注意传 i 而不是 i1 path.pop_back(); // 撤销 } } };复杂度分析设n是候选数组长度target是目标和。维度复杂度说明时间复杂度O(n^(target/min)))最坏情况每个位置可以选 n 个数字空间复杂度O(target/min)递归栈深度 path 长度更精确时间复杂度与解的数量和递归深度有关最坏情况为指数级。关键细节1. 为什么递归时传i而不是i1传i允许重复选当前数字如[2,2,3]传i1不允许重复选如 40 题「组合总和 II」这是本题和 40 题的核心区别。2. 为什么用start参数start控制当前层从哪个位置开始遍历避免产生重复组合。例子candidates [2,3],target 5如果不用start[2,3]和[3,2]都会出现重复用start选了 2 后下一层只能从 2 开始含 2不能选 3 之前的3. 为什么target 0要返回因为和已经超过target继续加只会更大直接剪枝。4. 排序优化可选如果先对candidates排序可以在target candidates[i]时提前breaksort(candidates.begin(), candidates.end()); // ... for (int i start; i candidates.size(); i) { if (target candidates[i]) break; // 后面的更大直接结束 // ... }方法二动态规划完全背包代码实现class Solution { public: vectorvectorint combinationSum(vectorint candidates, int target) { vectorvectorvectorint dp(target 1); dp[0] {{}}; for (int c : candidates) { for (int j c; j target; j) { for (auto comb : dp[j - c]) { vectorint newComb comb; newComb.push_back(c); dp[j].push_back(newComb); } } } return dp[target]; } };复杂度时间 O(n × target × 解的数量)空间 O(target × 解的数量)缺点需要存储所有中间结果空间大。两种方法对比方法时间复杂度空间复杂度推荐度回溯 剪枝指数级O(target/min)⭐⭐⭐⭐⭐动态规划O(n × target × 解的数量)O(target × 解的数量)⭐⭐⭐总结要点说明核心思想回溯从 start 开始遍历可以重复选当前数字关键条件递归时传i允许重复用start避免重复组合终止条件target 0收集结果target 0剪枝时间复杂度指数级空间复杂度O(target/min)