Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, � , a_k) must be in non-descending order. (ie, a₁ ? a₂ ? � ? a_k).
• The solution set must not contain duplicate combinations.

 

For example, given candidate set 10,1,2,7,6,1,5 and target 8, 

A solution set is: 

[1, 7] 

[1, 2, 5] 

[2, 6] 

[1, 1, 6]

class Solution {public:    vector
     
      
        > ans;    vector
       
        
          > combinationSum2(vector
         
           &num, int target){        /**            10,1,2,7,6,1,5 and target 8,            [1, 7]             [1, 2, 5]             [2, 6]             [1, 1, 6]                        Each number in C may only be used once in the combination.        */        vector
          
            path; ans.clear(); if (num.size() == 0){ return ans; } //sort vector
           
            
              > num_counter; sort(num.begin(),num.end()); int counter = 1; for(int i = 1; i < num.size(); i++){ if (num[i] == num[i -1]){ counter++; }else{ num_counter.push_back(make_pair(num[i-1],counter)); counter = 1; } } num_counter.push_back(make_pair(num[num.size() -1],counter)); dfs(num_counter,path,target); return ans; } void dfs(vector
             
              
                > & candidates, vector
               
                 & path,int target){ if (target == 0){ ans.push_back(path); return; } if (target < 0){ return; } int j = 0; for(;j < candidates.size();j++){ if (path.empty()){ break; } if (candidates[j].first == path[path.size() -1]){ int c = 0; for(int m = 0; m < path.size(); m++){ if (path[m] == candidates[j].first){ c++; } } if (c < candidates[j].second){ break; } }else if (candidates[j].first > path[path.size() -1]){ break; } } for(int i = j; i < candidates.size() && target - candidates[i].first >= 0; i++){ //candidates 事先排好序 path.resize(path.size() + 1); path[path.size() -1] = candidates[i].first; dfs(candidates,path,target - candidates[i].first); path.resize(path.size() - 1); } }};using namespace std;int main(int argc, char *argv[]) { int a[] = { 1,2,1,5,1,4,6,7}; vector
                
                  v(a,a+8); vector
                 
                  
                    > ans; Solution sol; ans = sol.combinationSum2(v,7); for(int i = 0; i < ans.size(); i++){ for(int j = 0; j < ans[i].size(); j++){ cout<<" " << ans[i][j]; } cout << endl; }}