链接
https://leetcode-cn.com/problems/combination-sum/
耗时
解题:? min (下次补上)
题解:10 min
题意
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
- 所有数字(包括 target)都是正整数。
- 解集不能包含重复的组合。
思路
很是撒比,之前会做的题,现在不会去重,用了set,结果慢的一匹,醉了。
其实每次不用从头找,从当前元素开始往后找就行,因为之前的各种情况都搜过了,再从头找也是重复的。而如果直接每次从当前元素开始往后找,每种情况都是全新的,还不用去重了!!!
基本思路就是暴搜,当前 数组的和 达到 目标值的话记录进结果,大于 目标值说明不行,直接舍弃。
时间复杂度:不会算
AC代码
class Solution {
private:
int n, target;
set<vector<int>> ans;
public:
void dfs(int res, vector<int> tmp, vector<int>& candidates) {
if(res > target) return ;
if(res == target) {
sort(tmp.begin(), tmp.end());
ans.insert(tmp);
return ;
}
for(int i = 0; i < n; ++i) {
tmp.push_back(candidates[i]);
dfs(res+candidates[i], tmp, candidates);
tmp.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
this->target = target;
n = candidates.size();
dfs(0, {}, candidates);
vector<vector<int>> vans;
for(auto x : ans) {
vans.push_back(x);
}
return vans;
}
};
2019年10月(一年前)
class Solution {
private:
vector<vector<int>> ans;
vector<int> path;
vector<int> candidates;
int target;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
this->candidates = candidates;
this->target = target;
sort(this->candidates.begin(), this->candidates.end());
core(0, 0);
return ans;
}
void core(int sum, int pre) {
if(sum == target) {
ans.push_back(path);
return ;
}
for(int i = pre; i < candidates.size() && sum + candidates[i] <= target; ++i) {
path.push_back(candidates[i]);
core(sum+candidates[i], i);
path.pop_back();
}
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)