LeetCode 中级 - 组合总和II(105)
2024-10-19 04:21:03
给定一个数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的每个数字在每个组合中只能使用一次。
说明:
- 所有数字(包括目标数)都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates =[10,1,2,7,6,1,5]
, target =8
,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
思路:数组未说明是否含义重复元素,这题同组合总和类型,但是需要注意判重, 每个数字在每个组合中只能使用一次则下一次递归时,start++,
为了避免数组中含有重复元素的情况,先将candidates排好序,进行处理。
class Solution {
public:
void dfs(vector<int> candidates,int start,int target,vector<int> item,vector<vector<int> >&res)
{
if(target<)
return ;
if(target==)
{
res.push_back(item);
return ;
}
for(int i=start;i<candidates.size();i++)
{
if(i>start&&candidates[i]==candidates[i-]) continue; //判重处理
item.push_back(candidates[i]);
dfs(candidates,i+,target-candidates[i],item,res);//i+1
item.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int> >res;
vector<int> item;
sort(candidates.begin(),candidates.end());//排序
dfs(candidates,,target,item,res);
return res;
}
};
最新文章
- Workload Automation分析及其使用
- STM32f103 定时器之编码器接口模式
- 通过实现Countable接口来调用count函数
- Oracle function real_st_astext,解决ArcSDE中st_astext函数返回字符串结构异常问题
- 解决eclipse配置Tomcat时找不到server选项
- [itint5]合并K个有序链表
- Tree of Life (easy)
- 深入理解Stream流水线
- js监听浏览器离开页面操作
- 随聊——Python的前世今生
- 登录测试用例sql语句注入
- java调用webservice,restful
- codeforces 3b之贪心算法
- []、()、None的区别
- CAS SSO单点登录实例
- 使用JavaScript获取URL中的参数(两种方法)
- 通过http上下文判断是否是Ajax请求
- android Keycode 完全对照表
- CAT架构的应用与实践 IT大咖说 - 大咖干货,不再错过
- windows server2012部署Cognos问题小结