Subsets
Given a set of distinct integers, return all possible subsets.
Notice
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
Example
If S = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
Challenge
Can you do it in both recursively and iteratively?
解题思路
一、DFS
要求一是子集中元素为升序，故先对原数组进行排序。要求二是子集不能重复，于是将原题转化为数学中的组合问题，使用深度优先搜索（DFS）进行穷举求解。
借用参考链接 1 中的解释，具体穷举过程可以用图示和函数运行的堆栈图理解，以数组[1, 2, 3]为例进行分析，下图所示为list及result动态变化的过程，箭头向下表示list.add及result.add操作，箭头向上表示list.remove操作。为了确保所有的情况都能够遍历到，在list加入一个元素后，还需要删除该元素以恢复原状态。
函数dfs(result, list, nums, 0)则表示将以list开头的所有组合全部加入result。当list是[1]时，对应图中步骤 2~7 ，依次将[1, 2], [1, 2, 3], [1, 3]全部添加到result中。
算法复杂度
- 时间复杂度：在本题中解的个数为
2^n，产生一个解的复杂度最坏可以认为是n，故算法时间复杂度的上界可以认为是O(n* 2^n)。 - 空间复杂度：使用临时空间
list保存中间结果，list最大长度为数组长度，故空间复杂度近似为O(n)。
易错点
- 记得给原始数组排序，以确保最终子数组是非降的。
Java 实现：
class
Solution
{
/**
*
@param
nums: A set of numbers.
*
@return
: A list of lists. All valid subsets.
*/
public
ArrayList
<
ArrayList
<
Integer
>
>
subsets(
int
[] nums) {
ArrayList
<
ArrayList
<
Integer
>
>
result =
new
ArrayList
<
ArrayList
<
Integer
>
>
();
// 注意：此处int型数组取长度无需括号()
if
(nums ==
null
|| nums.length ==
0
) {
result.add(
new
ArrayList
<
Integer
>
());
// when nums = [], return [[]]
return
result;
}
ArrayList
<
Integer
>
list =
new
ArrayList
<
Integer
>
();
Arrays.sort(nums);
dfs(result, list, nums,
0
);
return
result;
}
private
void
dfs
(ArrayList
<
ArrayList
<
Integer
>
>
result,
ArrayList
<
Integer
>
list,
int
[] nums,
int
pos)
{
result.add(
new
ArrayList
<
Integer
>
(list));
for
(
int
i = pos; i
<
nums.length; i++) {
list.add(nums[i]);
dfs(result, list, nums, i +
1
);
list.remove(list.size() -
1
);
//移除最后一个元素
}
}
}
二、Bit Map
一共2^n个子集，每个子集对应0 … 2^n - 1之间的一个二进制整数，该整数一共n个bit位，用第i个bit位的取值1或0表示nums[i]在或不在集合中，我们只需遍历完所有的数字——对应所有的bit位可能性（外循环），然后转化为对应的数字集合——判断数字每一个bit的取值（内循环）——即可。
以nums = [1,2,3]举例
0 -
>
000 -
>
null -
>
[]
1 -
>
001 -
>
nums[0] -
>
[1]
2 -
>
010 -
>
nums[1] -
>
[2]
3 -
>
011 -
>
nums[0],nums[1] -
>
[1,2]
4 -
>
100 -
>
nums[2] -
>
[3]
5 -
>
101 -
>
nums[1],nums[2] -
>
[1,3]
6 -
>
110 -
>
nums[1],nums[2] -
>
[2,3]
7 -
>
111 -
>
nums[0],nums[1],nums[2] -
>
[1,2,3]
Java 实现：
class
Solution
{
/**
*
@param
nums: A set of numbers.
*
@return
: A list of lists. All valid subsets.
*/
public
ArrayList
<
ArrayList
<
Integer
>
>
subsets(
int
[] nums) {
// write your code here
if
(nums ==
null
|| nums.length ==
0
) {
return
new
ArrayList
<
ArrayList
<
Integer
>
>
();
}
ArrayList
<
ArrayList
<
Integer
>
>
result =
new
ArrayList
<
ArrayList
<
Integer
>
>
();
int
n = nums.length;
Arrays.sort(nums);
// 注意函数使用是Arrays.sort()
// 1
<
<
n = 100...0 , i的取值范围是0 ~ 2^n -1
// i用来遍历所有的比特位可能性
for
(
int
i =
0
; i
<
(
1
<
<
n); i++) {
ArrayList
<
Integer
>
subset =
new
ArrayList
<
Integer
>
();
for
(
int
j =
0
; j
<
n; j++) {
// j的取值范围是0 ~ n
// j用来判断n个bit位的取值是否为1
if
((i
&
(
1
<
<
j)) !=
0
) {
subset.add(nums[j]);
}
}
// for j
result.add(subset);
}
// for i
return
result;
}
}