首页 > 其他 > 详细

Leetcode 39

时间:2020-09-09 13:57:07      阅读:63      评论:0      收藏:0      [点我收藏+]
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;

#define REP(x, l, u) for(ll x = l;x<u;x++)
#define RREP(x, l, u) for(ll x = l;x>=u;x--)
#define se second
#define fi first
typedef vector<int> VI;
typedef unordered_map<int,int> UMAPI;
const ll mod = 1e9 + 7;
#define len(x) x.size()

class Solution {
    VI res;
    vector<VI> ans;
    int n;
    void search(VI& candidates, int target, int start){
        if (target == 0){
            ans.emplace_back(res);
            return;
        }
        for(int i = start; i < n; i++){
            if(target  - candidates[i] >= 0){
                res.push_back(candidates[i]);
                search(candidates, target - candidates[i], i);
                res.pop_back();
            }
            else break;
        }
    }
    
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        n = len(candidates);
        sort(candidates.begin(), candidates.end());
        search(candidates, target, 0);
        return ans;
    }
};

 

普通回溯题,说是剪枝,其实算是贪心吧……所以需要事先排序

Leetcode 39

原文:https://www.cnblogs.com/KakagouLT/p/13638111.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!