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 50. Pow(x, n)
-
[leetcode]不同路径三连击~
-
LeetCode——Department Highest Salary(花式使用IN以及GROUP BY)
-
LeetCode——Department Top Three Salaries(巧妙使用子查询)
-
LeetCode——Customers Who Never Order(灵活使用NOT IN以及IN)
-
leetcode 921. 使括号有效的最少添加(Python)
-
#leetcode刷题之路13-罗马数字转整数
-
#leetcode刷题之路48-旋转图像
-
#leetcode刷题之路46-全排列
-
LeetCode刷题第二天