力扣算法题—039组合求和

  1 #include "000库函数.h"
  2 
  3 //第一感觉使用回溯比较快
  4 //好激动，第一次使用回溯成功 96ms,37.1M
  5 
  6 
  7 class Solution {
  8 public:
  9     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
 10         vector<vector<int>>Res;
 11         if (candidates.size() == 0)return Res;            
 12         vector<int>v;//临时存放解            
 13         Combin(candidates, Res,v, target, 0, 0);        
 14         return Res;
 15     }
 16 
 17     void Combin(vector<int>candidates, vector<vector<int>>&Res, vector<int>&v, int target, int start, int sum) {
 18         if (sum == target) {
 19             Res.push_back(v);
 20             return;
 21         }
 22         else if (sum > target)
 23             return;
 24         for (int i = start; i < candidates.size(); ++i) {
 25             v.push_back(candidates[i]);
 26             Combin(candidates, Res, v, target, i, sum + candidates[i]);
 27             v.pop_back();//将数字退出
 28         }
 29     }
 30 
 31 };
 32 
 33 
 34 //博客答案
 35 //解法一
 36 class Solution {
 37 public:
 38     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
 39         vector<vector<int>> res;
 40         sort(candidates.begin(), candidates.end());
 41         for (int i = 0; i < candidates.size(); ++i) {
 42             if (candidates[i] > target) break;
 43             if (candidates[i] == target) { res.push_back({ candidates[i] }); break; }
 44             vector<int> vec = vector<int>(candidates.begin() + i, candidates.end());
 45             vector<vector<int>> tmp = combinationSum(vec, target - candidates[i]);
 46             for (auto a : tmp) {
 47                 a.insert(a.begin(), candidates[i]);
 48                 res.push_back(a);
 49             }
 50         }
 51         return res;
 52     }
 53 };
 54 
 55 //解法二
 56 //建立一个三维数组dp，这里dp[i]表示目标数为i的所有解法集合。
 57 //这里的i就从1遍历到target即可，对于每个i，我们都新建一个二维数组cur，
 58 //然后遍历candidates数组，如果遍历到的数字大于i，说明当前及之后的数字都无法组成i，
 59 //直接break掉。否则如果相等，那么把当前数字自己组成一个数组，并且加到cur中。
 60 //否则就遍历dp[i - candidates[j] - 1] 中的所有数组，如果当前数字大于数组的首元素，
 61 //则跳过，因为我们的结果要求是要有序的。否则就将当前数字加入数组的开头，
 62 //并且将数组放入cur之中即可，参见代码如下：
 63 
 64 class Solution {
 65 public:
 66     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
 67         vector<vector<vector<int>>> dp;
 68         sort(candidates.begin(), candidates.end());
 69         for (int i = 1; i <= target; ++i) {
 70             vector<vector<int>> cur;
 71             for (int j = 0; j < candidates.size(); ++j) {
 72                 if (candidates[j] > i) break;
 73                 if (candidates[j] == i) { cur.push_back({ candidates[j] }); break; }
 74                 for (auto a : dp[i - candidates[j] - 1]) {
 75                     if (candidates[j] > a[0]) continue;
 76                     a.insert(a.begin(), candidates[j]);
 77                     cur.push_back(a);
 78                 }
 79             }
 80             dp.push_back(cur);
 81         }
 82         return dp[target - 1];
 83     }
 84 };
 85 
 86 void T039() {
 87     vector<int> v;    
 88     vector<vector<int>>Res;
 89     Solution s;
 90     v = { 2, 3, 6, 7 };
 91     Res = s.combinationSum(v, 7);
 92     for (auto &a : Res) {
 93         for (auto b : a)
 94             cout << b << "  ";
 95         cout << endl;
 96     }
 97     cout << endl<<"*********"<< endl;
 98     v = { 2, 3,5 };
 99     Res = s.combinationSum(v, 8);
100     for (auto &a : Res) {
101         for (auto b : a)
102             cout << b << "  ";
103         cout << endl;
104     }
105     cout << endl << "*********" << endl;
106 
107 
108 
109 }