欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode练习题combination-sum

程序员文章站 2022-05-21 22:32:55
...

解题思路

本质是dfs,首先将candidates排序,candidates中的元素可以重复选用,若target为0,则用一个tmp数组复制当前cur数组并排序,在res中查看是否已有该结果,若没有则插入。若target不为零则在candidates中选满足小于等于target的元素并深度搜索,每次搜索结束要回溯,将该元素从cur中pop_back。

代码

class Solution {
public:
    void dfs(vector<int> &candidates,int target,vector<vector<int>> &res,vector<int> &cur){
        if(target == 0){
            vector<int>tmp;
            tmp.insert(tmp.end(),cur.begin(),cur.end());
            sort(tmp.begin(),tmp.end());
            if(find(res.begin(),res.end(),tmp) == res.end())
                res.push_back(tmp);
            return;
        }
        for(int i = 0;i < candidates.size();i++){
            if(target - candidates[i] >= 0){
                cur.push_back(candidates[i]);
                dfs(candidates,target - candidates[i],res,cur);
                cur.pop_back();
            }
        }
    }
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int>>res;
        vector<int>cur;
        sort(candidates.begin(),candidates.end());
        dfs(candidates,target,res,cur);
        return res;
    }
};
相关标签: leetcode练习