题目描述给你一个无重复元素的整数数组candidates和一个目标整数target找出candidates中可以使数字和为目标数target的 所有不同组合并以列表形式返回。你可以按任意顺序返回这些组合。candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同则两种组合是不同的。对于给定的输入保证和为target的不同组合数少于150个。提示1 candidates.length 302 candidates[i] 40candidates的所有元素互不相同1 target 40思路解析组合搜索回溯算法 / DFS 问题。回溯法用于找出全部的可能状态并进行筛选。① 每次选取一个数字加入当前组合② 同一个数字可以重复使用所以递归时下标从当前位置开始③ 当 target 减到0说明找到了一个组合④ 当 target 小于当前比较对象说明该组合错误停止继续搜索ps : chat-gpt 实在是太好用了代码解析class Solution { private: vectorvectorint result; // 结果 vectorint path; //当前路径 void backtrak(const vectorint candidates,int target, int start){ // 如果剩余target为0说明路径正确 if(target 0){ result.push_back(path); return; } // 从start开始遍历 for(int i start; i candidates.size();i){ // 如果当前比较元素大于target后面的没必要比较肯定都大于 if(candidates[i]target){ break; } // 将当前target的candidates[i]压入path中 path.push_back(candidates[i]); // 递归调用还是从i开始因为元素可以重复使用 backtrak(candidates,target-candidates[i],i); // 如果路径正确直接就return了不会进行到这条语句 // 这条语句执行说明路径错误了将上一次压入path的元素出栈 path.pop_back(); } } public: vectorvectorint combinationSum(vectorint candidates, int target) { // 先排序方便剪枝 sort(candidates.begin(),candidates.end()); backtrak(candidates,target,0); return result; } };拓展提升如果要求一个数组可能的全排列且不能有重复该怎么处理给定一个可包含重复数字的序列nums按任意顺序返回所有不重复的全排列。示例 1输入nums [1,1,2]输出[[1,1,2], [1,2,1], [2,1,1]]示例 2输入nums [1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]提示1 nums.length 8-10 nums[i] 10思路解析依旧是回溯法但需要添加剪枝条件。假设有两个相同的值如果之前选择了那么之后不能再选择不然会出现重复的问题。下图展示了如果不适用去重会发生什么。代码解析class Solution { public: vectorvectorint result; void backtrack(vectorint nums, int start) { if (start nums.size()) { result.push_back(nums); return; } // 用 set 记录当前位置已经使用过的元素 unordered_setint used; for (int i start; i nums.size(); i) { // 如果这个值已经在当前位置使用过跳过 if (used.count(nums[i])) continue; used.insert(nums[i]); swap(nums[start], nums[i]); backtrack(nums, start 1); swap(nums[start], nums[i]); } } vectorvectorint permuteUnique(vectorint nums) { sort(nums.begin(), nums.end()); backtrack(nums, 0); return result; } };