LeetCode--Combination Sum II

思路：类似于上一题，但是加了一个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 };