lintcode-153-数字组合 II
2024-08-24 07:31:56
153-数字组合 II
给出一组候选数字(C)和目标数字(T),找出C中所有的组合，使组合中数字的和为T。C中每个数字在每个组合中只能使用一次。
注意事项
所有的数字(包括目标数字)均为正整数。
元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。
解集不能包含重复的组合。样例
给出一个例子，候选数字集合为[10,1,6,7,2,1,5] 和目标数字 8 ,
解集为：[[1,7],[1,2,5],[2,6],[1,1,6]]标签
回溯法 数组 深度优先搜索
思路
使用回溯加递归的方式，需要先对原数组排序，另外需要注意筛除重复的结果集
code
class Solution {
public:
/**
* @param num: Given the candidate numbers
* @param target: Given the target number
* @return: All the combinations that sum to target
*/
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
// write your code here
int size = num.size();
if (size <= 0) {
return vector<vector<int> >();
}
sort(num.begin(), num.end());
vector<vector<int> > result;
vector<int> temp;
isInsert(result, temp, num, 0, 0, target);
return result;
}
void isInsert(vector<vector<int> > &result, vector<int> &temp, vector<int> &num, int current, int sum, int target) {
if (sum == target && !isExisted(result, temp)) {
result.push_back(temp);
return;
}
if (current < num.size() && sum < target) {
sum += num[current];
temp.push_back(num[current]);
isInsert(result, temp, num, current + 1, sum, target);
sum -= temp[temp.size() - 1];
temp.pop_back();
isInsert(result, temp, num, current + 1, sum, target);
}
}
bool isExisted(vector<vector<int> > &result, vector<int> &temp) {
for (int i = 0; i < result.size(); i++) {
if (temp.size() == result[i].size()) {
int ret = true;
for (int j = 0; j < temp.size(); j++) {
if (temp[j] == result[i][j]) {
ret = ret & true;
}
else {
ret = ret & false;
}
}
if (ret == true) {
return true;
}
}
}
return false;
}
};
最新文章
- nginx日常运维
- fir.im Weekly - iOS 保持界面流畅的技巧
- HTML基本知识
- Linux 系统编程
- 第二百四十天 how can I 坚持
- Lua从入门到精通
- tomcat中有关配置文件的说明
- PHP的curl常用的5种写法
- EditText 默认不获取焦点，弹出软键盘布局变形解决方案
- vs c++配置opencv（1）
- 第七章 DAO模式
- php操作mongodb的常用函数
- Java作业五（2017-10-15）
- C# Cache 设定过期时间的方法
- Android 之 tools:context和tools:ignore两个属性的作用
- Docker的入门使用（初探总结）
- Linux更改中国时区
- 6.Spring MVC SSM整合问题总结
- 从0开始学golang--1.1--连接ms sql server数据库
- 在pixi中使用你的自定义着色器