1 #include "000库函数.h" 2  3 //第一感觉使用回溯比较快 4 //96ms 5  6  7 class Solution { 8 public: 9     vector
     
      
       > combinationSum2(vector
       
        & candidates, int target) {10         vector
        
         
          >R;11         sort(candidates.begin(), candidates.end());12         if (candidates.size() == 0)return R;13         vector
          
           v;//临时存放解 14 Combin(candidates, R, v, target, 0, 0); 15 return R;16 }17 18 void Combin(vector
           
            candidates, vector
            
             
              >&Res, vector
              
               &v, int target, int start, int sum) {19 if (sum == target) {20 //sort(v.begin(), v.end());21 Res.push_back(v);22 return;23 }24 else if (sum > target)25 return;26 27 for (int i = start; i < candidates.size(); ++i) {28 if (i > start&&candidates[i] == candidates[i - 1])continue;//去除重复的组合 29 v.push_back(candidates[i]);30 Combin(candidates, Res, v, target, i + 1, sum + candidates[i]);//i+1是与上题的不同之处，不会出现重复使用元素31 v.pop_back();//将数字退出 32 }33 }34 35 };36 37 void T040() {38 vector
               
                 v;39 vector
                
                 
                  >Res;40 Solution s;41 v = { 10,1,2,7,6,1,5 };42 Res = s.combinationSum2(v, 8);43 for (auto &a : Res) {44 for (auto b : a)45 cout << b << " ";46 cout << endl;47 }48 cout << endl << "*********" << endl;49 /*v = { 2, 3,5 };50 Res = s.combinationSum(v, 8);51 for (auto &a : Res) {52 for (auto b : a)53 cout << b << " ";54 cout << endl;55 }56 cout << endl << "*********" << endl;57 */58 59 60 }