LeetCode

LeetCode-39 组合总和

nkul · 10月3日 · 2020年 · 21次已读

1、因为不限使用此数,故只能暴力破解无法优化;

2、第一个数选0个、选1个。。。选n个

3、第二个数选0个、选1个。。。选n个,此时要凑的总和为target – 第一个数 * 选的个数

class Solution {
public:
    vector> ans;
    vector path;
    vector> combinationSum(vector& c, int target) {
        dfs(c, 0 , target);
        return ans;
    }
    //u 数组c的下标,即选第u个数
    void dfs(vector& c , int u , int target){
        //凑出了target,添加到数组中
        if(target == 0) {
            ans.push_back(path);
            return;
        }
        //遍历到了最后一个还是没有凑出targe,无解
        if(u == c.size()) return;
        for(int i = 0; i * c[u] <= target ;i ++){
            dfs(c, u + 1, target - c[u] * i);
            path.push_back(c[u]);
        }
        //恢复现场,怎么使用的path,就怎么释放path
        for(int i = 0;c[u] * i <= target ;i++){
            path.pop_back();
        }
    }
};



0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!