文章目录
题目描述说明示例
题解代码
题目描述
给定一组不含重复元素的整数数组 nums ，返回该数组所有可能的子集（幂集）。
说明
解集不能包含重复的子集。
示例
输入
第一行输入数组元素个数第二行输入数组各个元素 输出
打印输出该数组所有的子集
输入:
3
1 2 3
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
题解
本题可以采用子集树的思想处理。
对于其中某个子集来说，任意一个元素要么在这个集合中，要么不在，可以使用一位二进制数来标记，1 代表在，0 代表不在。这样可以取
0
2
<
s
u
p
>
N
<
/
s
u
p
>
(
N
为
数
组
元
素
个
数
)
{0 ~ 2<sup>N</sup>} (N 为数组元素个数)
0 2<sup>N</sup>(N为数组元素个数) 表示每一个子集，每一个数的二进制数的每一位标识数组中每一个数的状态。这样遍历一遍即可找出所有子集。
此题也可以利用递归和回溯法求解。
代码
#include <iostream>
#include <vector>
using namespace std
;
vector
<vector
<int> > sub_sets(vector
<int> nums
)
{
vector
<vector
<int> > ans
;
vector
<int> v
;
int max
= (1 << nums
.size());
for (int i
= 0, j
= 0, k
= 0; i
< max
; i
++) {
v
.clear();
for (j
= i
, k
= 0; j
> 0; j
>>= 1)
{
if ((j
& 1) == 1)
{
v
.push_back(nums
[k
]);
}
k
++;
}
ans
.push_back(v
);
}
return ans
;
}
int main()
{
int n
= 0, num
= 0;
vector
<int> nums
;
cin
>> n
;
while (n
--)
{
cin
>> num
;
nums
.push_back(num
);
}
vector
<vector
<int> > sets
= sub_sets(nums
);
vector
<int> v
;
cout
<< "[" << endl
;
for (unsigned int i
= 0, j
= 0; i
< sets
.size(); i
++)
{
v
= sets
[i
];
cout
<< " [";
for (j
= 0; j
< v
.size(); j
++)
{
cout
<< v
[j
] << ",";
}
cout
<< "]," << endl
;
}
}
返回顶部
