©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>组合总和
<>暴力回溯（无剪枝，时间复杂度高）
class Solution { public: vector<vector<int>> result; vector<int> path; int sum;
void backtracking(vector<int>& candidates, int target , int sum) { //检测目标大于时返回
if(sum > target) return; if(sum == target) { //排序后发现是新结果插入 vector<int> tmp(path.
begin(),path.end()); sort(tmp.begin(),tmp.end()); auto it = find(result.begin(),
result.end(),tmp); if(it == result.end()) result.push_back(tmp); return; }
//无任何限制回溯 for(int i = 0 ; i < candidates.size() ;i++) { path.push_back(
candidates[i]); backtracking(candidates,target,sum+candidates[i]); path.pop_back
(); } return; } vector<vector<int>> combinationSum(vector<int>& candidates, int
target) { backtracking(candidates,target,0); return result; } };
<>回溯剪枝
class Solution { public: vector<vector<int>> result; vector<int> path; int sum;
void backtracking(vector<int>& candidates, int target , int sum , int indnx) {
if(sum > target) return; if(sum == target) { result.push_back(path); return; }
//剪枝，因为之前已经对输入进行排序，当发现加上i点的值大于目标后，后面的也都大于 for(int i = indnx ; i < candidates.
size() && sum+candidates[i] <= target ;i++) { path.push_back(candidates[i]);
//递归的下一个指针和当前一样都是i，不是i+1 //因为一个数可以重复的使用，不能重复是i+1 backtracking(candidates,target,
sum+candidates[i] , i); path.pop_back(); } return; } vector<vector<int>>
combinationSum(vector<int>& candidates, int target) { //对输入进行排序，方便后面循环 sort(
candidates.begin(),candidates.end()); backtracking(candidates,target,0,0);
return result; } };
<>二刷
class Solution { public: vector<int> path; vector<vector<int>> result; int
sumNum=0; void dfs(vector<int>& candidates, int target,int fir) { if(sumNum >
target) return; if(sumNum == target) { result.push_back(path); return; } for(int
i=fir ; i<candidates.size() ; i++) { path.push_back(candidates[i]); sumNum +=
candidates[i]; dfs(candidates,target,i); sumNum -= candidates[i]; path.pop_back(
); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates,target,0); return result; } };