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

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, 

A solution set is: 

[7] 

[2, 2, 3] 

class Solution {private:    vector
     
      
        > ivvec;public:    vector
       
        
          > combinationSum(vector
         
           &candidates, int target) {        vector
          
            ivec; sort(candidates.begin(), candidates.end()); combinationSum(candidates, 0, target, ivec); return ivvec; } void combinationSum(vector
           
             &candidates, int beg, int target, vector
            
              ivec) { if (0 == target) { ivvec.push_back(ivec); return; } for (int idx = beg; idx < candidates.size(); ++idx) { if (target - candidates[idx] < 0) break; ivec.push_back(candidates[idx]); combinationSum(candidates, idx, target - candidates[idx], ivec); ivec.pop_back(); } }};
            
           
          
         
        
       
      
     

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 (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• 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] 

与上题差别不大。依然是用DFS，基本的问题在于怎样去重。

能够添加一个剪枝: 当当前元素跟前一个元素是同样的时候。假设前一个元素被取了，那当前元素能够被取，也能够不取，反过来假设前一个元素没有取。那我们这个以及之后的所以同样元素都不能被取。

(採用flag的向量作为标记元素是否被选取)

class Solution {private:    vector
     
      
        > ivvec;    vector
       
         flag;public:    vector
        
         
           > combinationSum2(vector
          
            &num, int target) { vector
           
             ivec; sort(num.begin(), num.end()); flag.resize(num.size()); for (int i = 0; i < flag.size(); ++i) flag[i] = false; combinationSum2(num, 0, ivec, target, 0); return ivvec; } void combinationSum2(vector
            
              &num, int beg, vector
             
               ivec, int target, int sum) { if (sum > target) return; if (sum == target) { ivvec.push_back(ivec); return; } for (int idx = beg; idx < num.size(); ++idx) { if (sum + num[idx] > target) continue; if (idx != 0 && num[idx] == num[idx - 1] && flag[idx - 1] == false) continue; flag[idx] = true; ivec.push_back(num[idx]); combinationSum2(num, idx + 1, ivec, target, sum + num[idx]); ivec.pop_back(); flag[idx] = false; } }};
             
            
           
          
         
        
       
      
     

版权声明：本文博主原创文章。博客，未经同意不得转载。