首页 > 代码库 > LeetCode--Combination Sum II

LeetCode--Combination Sum II

2024-07-15 14:21:44   212人阅读

思路：类似于上一题，但是加了一个index数组记录结果里面已经存放的元素索引，

用来判断当前的元素是否和上一个相同并且上一个是否使用过。

主要为了解决重复解的问题。

 1 class Solution { 2 public: 3     vector<vector<int> >ans; 4     vector<vector<int> > combinationSum2(vector<int> &num, int target) { 5         if(num.size() == 0) 6             return ans; 7         sort(num.begin(),num.end()); 8         vector<int> res; 9         vector<int> index;10         calSum(num,target,0,res,index);11         return ans;12     }13     void calSum(vector<int> &num,int target,int s,vector<int> &res,vector<int> &index)14     {15         if(target < 0)16             return;17         if(target == 0)18         {19             ans.push_back(res);20             return;21         }22         int i;23         for(i = s ; i < num.size() ; ++i)24         {25             if(i >0 && index[index.size()-1] != i-1 && num[i] == num[i-1])26                 continue;27             index.push_back(i);28             res.push_back(num[i]);29             calSum(num,target-num[i],i+1,res,index);30             res.pop_back();31             index.pop_back();32         }33         return;34     }35 };

 


联系
我们