【一天一道LeetCode】#40. Combination Sum II
2024-10-08 00:16:09
一天一道LeetCode系列
(一)题目
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
(二)解题
具体思路与【一天一道LeetCode】39. Combination Sum这篇博文一样,采用动态规划和回溯法进行求解。
/*
和上一题的思路一样,区别是数字不能重复查找,但Vector中允许有重复的数字
具体改动请看代码注释
*/
class Solution {
public:
vector<vector<int>> ret;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
for(int idx = 0;idx<candidates.size();idx++)
{
if(idx-1>=0 && candidates[idx] == candidates[idx-1]) continue;//避免重复查找
else
{
if(candidates[idx]<=target)
{//如果小于则调用动态规划函数
vector<int> tmp;
tmp.push_back(candidates[idx]);
combinationDfs(candidates,tmp,idx,target-candidates[idx]);
}
}
}
return ret;
}
void combinationDfs(vector<int>& candidates ,vector<int>& tmp, int start ,int target)
{
if(target == 0){
ret.push_back(tmp);
return;
}
for(int i = start+1 ; i < candidates.size() ; i++)//从start+1开始查找,避免了数字重复查找
{
if(candidates[i] < target){
tmp.push_back(candidates[i]);
combinationDfs(candidates,tmp,i,target-candidates[i]);
tmp.pop_back(); //回溯
}
else if(candidates[i] == target){
tmp.push_back(candidates[i]);
ret.push_back(tmp);
tmp.pop_back();//回溯
}
else
{
return;
}
while(i+1< candidates.size()&&candidates[i]==candidates[i+1]) i++;//去除重复的查找
}
}
};
最新文章
- 学习javascript数据结构(三)——集合
- iOS:CYLTabBarController【低耦合集成TabBarController】
- 数据结构算法C语言实现(二十七)--- 7.2图的遍历
- JS图表插件(柱形图、饼状图、折线图)
- 【转载】 postman使用教程
- 浅析JavaScript函数的参数
- webform处理过程
- 一个小型的DBHelper的诞生(1)
- 基于visual Studio2013解决算法导论之052深度优先
- [server]nginx 一系列命令
- iOS UITabView简写瀑布流
- kafka副本机制之数据可靠性
- HTML/CSS初步了解
- PHP服务器时差8小时的解决办法
- Storm实现实时大数据分析(storm介绍,与Hadoop比较,)
- jsp获取当前项目跟路径
- 使用grep排除空行和注释行
- redis mongodb mysql 三大数据库的更简单的批量操作。批量任务自动聚合器。
- angular学习笔记(二十六)-$http(4)-设置请求超时
- 使用 npm 安装 Vue
热门文章
- UILabel 调整行间距
- Dynamics CRM 打开数据加密报错及修改用户邮件保存报错的解决方法
- Dynamics CRM2013 6.1.1.1143版本插件注册器的一个bug
- springMVC源码分析--DispatcherServlet请求获取及处理
- Android开发之Intent.Action 各种Action的常见作用
- Java提升篇之反射的原理(二)
- 百度地图SDK3.4的使用
- Android初级教程通过简要分析“土司”源码,来自实现定义土司理论探讨
- Cocos2D中Action的进阶使用技巧(一)
- Android 推送和统计最优轮循(心跳策略)探究实践