使用深度优先搜索解决。

#include 
     
      #include 
      
       #include 
       
        using namespace std;class Solution {public:    vector
        
         
           > combinationSum(vector
          
            &candidates, int target) { vector
           
             tmpresult; tmpresult.clear(); combinationSumCore(candidates, 0, target, tmpresult); return res; } void combinationSumCore(vector
            
              &candidates, int curr, int target, vector
             
               tmpresult){ if (0 == target){ res.push_back(tmpresult); return; } if (curr == candidates.size()) return; for (int i = 0; i <= target/candidates[curr]; i++){ vector
              
                tmpresult1(tmpresult); for (int j = 0; j < i; j++) tmpresult1.push_back(candidates[curr]); combinationSumCore(candidates, curr+1, target-i*candidates[curr], tmpresult1); } }private: vector
               
                
                  > res;};int main(){ vector
                 
                   vec; vec.push_back(1); Solution s; s.combinationSum(vec, 2); return 0;}
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

 

 

 

 

 

EOF