【Leetcode】【Medium】Combination Sum II
2024-09-03 16:59:30
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]
解题思路:
求序列的排列组合,典型的回溯算法思想。
如果有兴趣查看Combination Sum版本I,请点击链接。
版本一中candidate没有重复,但是可以允许重复使用candidates中的元素;即,对于{1,2,3,4},选择了1,还可以继续在{1,2,3,4}中选择,返回序列不会出现重复结果;
版本二(本题)设置candidate有重复,但是每个candidate只能使用一次;即,对于{1,2,2,3,4},选择了1,只能继续在{2,2,3,4}中选择;
但是,因为candidate中“2”有重复,如果需要选择“2”,只能选择“第一个2”,不能选择“第二个2”;
因为如果target是10,选择第一个2会返回结果{1,2,3,4},但是选择第二个2,也会出现相同序列{1,2,3,4};造成返回队列包含重复结果;
选择“第一个2”后,还能继续从{2,3,4}中挑选下一个数,因此不会漏选;
代码:
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> lst;
vector<int> ans;
sort(candidates.begin(), candidates.end());
Backtracking(lst, ans, candidates, , target);
return lst;
} void Backtracking(vector<vector<int>> &lst, vector<int> ans, vector<int> candidates, int idx, int left) {
for (int i = idx; i < candidates.size(); ++i) {
if (i > idx && candidates[i] == candidates[i-])
continue;
int cur_v = left - candidates[i];
if (cur_v == ) {
ans.push_back(candidates[i]);
lst.push_back(ans);
return;
} if (cur_v > ) {
ans.push_back(candidates[i]);
Backtracking(lst, ans, candidates, i + , cur_v);
ans.pop_back();
} else {
break;
}
}
return;
}
};
最新文章
- N-Tier Entity Framework开源项目介绍
- Swift - 界面的跳转模式
- ps(process status)
- webService 部署以后参数输入框不能显示
- cocos2d 中显示系统时间
- An Introduction to Garbage Collection(垃圾回收简介)
- web api control注册及重写DefaultHttpControllerSelector、ApiControllerActionSelector、ApiControllerActionInvoker
- Android -- 获取汉字的首字母
- 一次JQuery性能优化实战
- 安装oracle11g未找到文件WFMLRSVCApp.ear文件
- 几道C语言的题目!
- Gentoo本地化设置--Locale系统介绍
- LeetCode 34. Search for a Range (找到一个范围)
- vue中的checkbox全选和反选
- 特殊权限 SUID、SGID、Sticky
- 基于nodemailer使用阿里云企业邮箱发送邮件(526错误的解决)
- Django组件 之 ookie 和 session
- js用replaceAll全部替换的方法
- C#_02.13_基础四_.NET方法
- ArcGIS鼠标滚轮方向之代码篇