题目描述：
给定一个含不同整数的集合，返回其所有的子集。
注意事项：
子集中的元素排列必须是非降序的，解集必须不包含重复的子集。
样例：
如果 S = [1,2,3]，有如下的解：
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
思路分析（对于没有重复元素）：
我们可以先看一个例子[1]、[1,2]、[1,2,3]这三个的子集分别是什么？
[1]的子集是[1]、[]
[1,2]的子集是[1]、[1，2]、[2]、[]
[1,2,3]的子集是[1]、[1，2]、[2]、[1，3]、[1，2，3]、[2，3]、[3]、[]
我们发现[1,2,3]是在[1,2]的所有子集尾部添加了3之后合并[1,2]的子集就是[1,2,3]的子集。
[1,2]也是在[1]的所有子集尾部添加了2，然后合并[1]的子集就是[1,2]的子集。
通过上面的例子，我们可以发现我们可以通过n次循环，每一次在上一次的基础上进行操作就可以了。
代码详解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
/*
* @param nums: A set of numbers
* @return: A list of lists
*/
vector<vector<int>> subsets(vector<int> &nums) {
// write your code here
vector<vector<int>>res;
if(nums.size()==0)
{
res.push_back(nums);
return res;
}
//vector<vector<int>>res;
vector<int>temp;
temp.push_back(nums[0]);
res.push_back(temp);
temp.clear();
for(int i=1;i<nums.size();i++)
{
int length=res.size();
for(int j=0;j<length;j++)
{
temp.assign(res[j].begin(),res[j].end());
temp.push_back(nums[i]);
res.push_back(temp);
temp.clear();
}
temp.push_back(nums[i]);
res.push_back(temp);
temp.clear();
}
res.push_back(temp);
return res;
}
};思路分析（对于有重复元素）：
我们还是先看一个例子[1]、[1,1]、[1,2,2]这三个的子集分别是什么？
[1]的子集是[1]、[]
[1,1]的子集是[1]、[1，1]、[]
[1,2]的子集是[1]、[1，2]、[2]、[]
[1,2,2]的子集是[1]、[1，2]、[2]、[1，2，2]、[2，2]、[]
通过上面的我们发现当2跟2重复时，其只在[1,2]中2添加的子集[1，2]、[2]的尾部上添加上2，得到[1，2，2]、[2，2]，将其与[1,2]的子集合并，这样就得到了[1,2,2]的子集。
同理，[1,1]我们将[1]添加的子集看作是[1]，这样其就在[1]的后面添加上1，两个合并就得到[1，1]的子集。
通过上面的例子我们发现，当出现两个重复的数字时，后面的一个数字只在上一个数字增加的子集上进行操作，而不是对所有的进行操作。
代码详解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class Solution {
public:
/*
* @param nums: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
// write your code here
vector<vector<int>>res;
if(nums.size()==0)
{
res.push_back(nums);
return res;
}
sort(nums.begin(),nums.end());
vector<int>temp;
temp.push_back(nums[0]);
res.push_back(temp);
temp.clear();
int *count=new int[nums.size()+1];
count[0]=1;
for(int i=1;i<nums.size();i++)
{
if(nums[i]==nums[i-1])
{
int length=count[i-1];
count[i]=length;
cout<<"length is "<<length<<" "<<res.size()<<endl;
//cout<<res.size()-1<<" "<<res.size()-1-length<<endl;
int n=res.size()-length;
//cout<<n-1<<endl;
for(int j=res.size()-1;j>n-1;j=j-1)
{
cout<<"sunshine"<<endl;
temp.assign(res[j].begin(),res[j].end());
printvector(temp);
temp.push_back(nums[i]);
//printvector(temp);
res.push_back(temp);
temp.clear();
printvector2D(res);
}
cout<<"sunshine1995"<<endl;
}
else{
int length=res.size();
count[i]=length+1;
for(int j=0;j<length;j++)
{
temp.assign(res[j].begin(),res[j].end());
temp.push_back(nums[i]);
res.push_back(temp);
temp.clear();
}
temp.push_back(nums[i]);
res.push_back(temp);
temp.clear();
printvector2D(res);
}
}
res.push_back(temp);
return res;
}
void printvector(vector<int> res)
{
for(int i=0;i<res.size();i++)
{
cout<<res[i]<<" ";
}
cout<<endl;
}
void printvector2D(vector<vector<int>> res)
{
for(int i=0;i<res.size();i++)
{
cout<<"[";
for(int j=0;j<res[i].size();j++)
{
cout<<res[i][j]<<" ";
}
cout<<"]"<<endl;
}
}
};最后
以上就是狂野烤鸡最近收集整理的关于lintcode---子集（带重复元素和不带重复元素的两种解法）的全部内容，更多相关lintcode---子集（带重复元素和不带重复元素内容请搜索靠谱客的其他文章。
发表评论 取消回复