Subsets and Subsets II (回溯，DFS，组合问题)
2024-09-30 18:30:49
Given a set of distinct integers, S, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
] 该题和Combinations很类似，只不过是k需要从0到size中取值。
class Solution {
private:
vector<vector<int>> res;
vector<int> s;
public:
void tra(int k,int start,int dep,vector<int> temp)
{
if(dep==k){
res.push_back(temp);
return;
}
for(int i=start;i<s.size();++i){
temp.push_back(s[i]);
tra(k,i+,dep+,temp);//是i+1，而不是start+1
temp.erase(temp.end()-);
}
}
vector<vector<int>> subsets(vector<int> &S) {
s=S;
sort(s.begin(),s.end());
vector<int> temp;
for(int k=;k<=s.size();++k){
tra(k,,,temp);
}
return res;
}
};
我的分析图：
Subsets 2
Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
class Solution {
private:
vector<vector<int>> res;
vector<int> s;
public:
void tra(int k,int start,int dep,vector<int> temp)
{
if(dep==k){
for (int i=;i<res.size();++i)
{
if(res[i]==temp) return;
}
res.push_back(temp);
return;
}
for(int i=start;i<s.size();++i){
temp.push_back(s[i]);
tra(k,i+,dep+,temp);
temp.erase(temp.end()-);
}
}
vector<vector<int>> subsetsWithDup(vector<int> &S) {
s=S;
sort(s.begin(),s.end());
vector<int> temp;
res.push_back(temp);
for(int k=;k<=s.size();++k){
tra(k,,,temp);
}
return res;
}
};
最新文章
- Hadoop中wordcount程序
- 基于ASP.NET MVC的热插拔模块式开发框架(OrchardNoCMS)--瘦身计划
- WCF小白初试 错误之一：“有零个应用程序终结点”的解决办法
- Imread函数不好使的替用方法
- Linux系统启动流程（2）
- [渣译文] SignalR 2.0 系列：SignalR的高频实时通讯
- shell脚本获取随机数random
- lua lua解读
- （转）spring aop(下）
- 冲刺No.4
- 【JavaScript】封装实用方法【持续积累】
- 深入学习vue指令，自定义指令解决开发痛点
- content_type
- Ubuntu14设置静态IP的地方
- 通过NAT转发实现私网对外发布信息
- 缓存淘汰算法（LFU、LRU、ARC、FIFO、MRU）分析
- Linux 防火墙iptables命令详解
- New Concept English Two 26 70
- 第195天：js---函数对象详解（call、apply）
- 概率dp - UVA 11021 Tribles