[LeetCode]Combination Sum II-白红宇

[LeetCode]Combination Sum II

阅读量：4150 次

发布时间：2019-05-25

本文共 3023 字，大约阅读时间需要 10 分钟。

class Solution {	//DFS	//sort candidates first and then DFS	//note here how to get the unique combination: !(index != 0 && candidates[index] == candidates[index-1] && !used[index-1])	//and the cut off trick: sumNow+candidates[index] <= targetpublic:	vector
   
    
      > combinationSum2(vector
     
       &candidates, int target) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		sort(candidates.begin(), candidates.end());		vector
      
       
        > ans;		vector
        
          path; vector
         
           used(candidates.size(), false); combinationSum_aux(0, 0, target, path, ans, candidates, used); return ans; } void combinationSum_aux( int index, int sumNow, int target, vector
          
           & path, vector
           
            
             >& ans, vector
             
              & candidates, vector
              
               & used ) { //throw std::exception("The method or operation is not implemented."); if(sumNow == target) { ans.push_back(path); return; } if(index >= candidates.size()) return; if( !(index != 0 && candidates[index] == candidates[index-1] && !used[index-1]) && sumNow+candidates[index] <= target) {//cut off here is very important used[index] = true; path.push_back(candidates[index]); combinationSum_aux(index+1, sumNow+candidates[index], target, path, ans, candidates, used); path.pop_back(); used[index] = false; } combinationSum_aux(index+1, sumNow, target, path, ans, candidates, used); }};

second time

class Solution {public:    void combinationSumUtil(vector
   
    & candidates, int target, int curIdx, vector
    
     & curPath, vector
     
      & used, vector
      
       
         >& allPath)    {        if(target == 0)        {            allPath.push_back(curPath);            return ;        }        if(target < 0) return;        if(curIdx >= candidates.size()) return;                        if(curIdx >= 1 && candidates[curIdx] == candidates[curIdx-1] && used[curIdx-1] == false) combinationSumUtil(candidates, target, curIdx+1, curPath, used, allPath);        else        {            curPath.push_back(candidates[curIdx]);            used[curIdx] = true;            combinationSumUtil(candidates, target-candidates[curIdx], curIdx+1, curPath, used, allPath);            used[curIdx] = false;            curPath.pop_back();            combinationSumUtil(candidates, target, curIdx+1, curPath, used, allPath);        }    }    vector
        
         
           > combinationSum2(vector
          
            &candidates, int target) { // Start typing your C/C++ solution below // DO NOT write int main() function sort(candidates.begin(), candidates.end()); vector
           
             curPath; vector
            
             
               > allPath; vector
              
                used(candidates.size(), false); combinationSumUtil(candidates, target, 0, curPath, used, allPath); return allPath; }};