【算法】给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
题目
Subsets : https://leetcode.com/problems/subsets/
如果S=[1,2,3], 给出所有子集。
如:
[↵ [3],↵ [1],↵ [2],↵ [1,2,3],↵ [1,3],↵ [2,3],↵ [1,2],↵ []↵ ]
解题思路
1、回溯法动态规划。
回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
2、位运算 迭代法实现 子集枚举
3、递归法实现子集枚举
4、常规思路,非递归
解题思路一: 位运算 迭代法实现 子集枚举
思路与算法
数组中的每一个数字都有选和不选两种状态,我们可以用0和1表示,0表示不选,1表示选择。如果数组的长度是n,那么子集的数量就是2^n。比如数组长度是3,就有8种可能
假设原序列中元素的总数为 n。
原序列中的每个数字 a(i) 的状态可能有两种,即「在子集中」和「不在子集中」。
我们用 1 表示「在子集中」,0 表示不在子集中,那么每一个子集可以对应一个长度为 n 的 0/1 序列,第 i 位表示 a(i) 是否在子集中。
例如,n = 3n=3 ,a = { 5, 2, 9 } 时:
0/1序列 | 子集 | 0/1 序列对应的二进制数 |
---|---|---|
000000 | {} | 0 |
001001 | {9} | 1 |
010010 | {2} | 2 |
011011 | {2,9} | 3 |
100100 | {5} | 4 |
101101 | {5,9} | 5 |
110110 | {5,2} | 6 |
111111 | {5,2,9} | 7 |
0/1 序列对应的二进制数正好从 00 到 2^n - 1。我们可以枚举 mask ∈ [0, 2^n−1],mask 的二进制表示是一个 0/1 序列,我们可以按照这个 0/1 序列在原集合当中取数。
当我们枚举完所有 2^n个 mask,我们也就能构造出所有的子集。
示例图
代码实现
public static List<List<Integer>> method4(Integer[] nums) {
// 子集列表
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
int len = nums.length;
// 获得所有子集数. 1<<nums.length 等价于 2^nums.length,对于n个数字的数组,共2^n个子集
//子集的长度是2的nums.length次方,这里通过移位计算
int soo = 1 << len; // or (int) Math.pow(2, len);
System.out.println("子集数量:" + soo);
//遍历从0到length中间的所有数字,根据数字中1的位置来找子集
for (int mask = 0; mask < soo; ++mask) {
temp.clear();
for (int j = 0; j < len; ++j) {
// 查看对应的二进制
// String binaryMask = Integer.toBinaryString(mask);
// String binarySpo = Integer.toBinaryString(1 << j);
// ((mask >> j) & 1) 指 如果数字 mask 的某一个位置是1,就把数组中对应的数字添加到集合
// 此处两种写法均可以:` (mask & (1 << j)) != 0 ` 或者 ` ((mask >> j) & 1) == 1 `
if (((mask >> j) & 1) == 1) {
temp.add(nums[j]);
}
}
// 添加一个计算出的子集
res.add(new ArrayList<>(temp));
}
return res;
}
输出:
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
复杂度分析
- 时间复杂度:O(n * 2^n)。一共 2^n 个状态,每种状态需要 O(n) 的时间来构造子集。
- 空间复杂度:O(n)。即构造子集使用的临时数组 t 的空间代价。
解题思路二: 递归法实现子集枚举
代码实现
public static List<List<Integer>> method2(Integer[] nums) {
// 子集列表
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
dfs(res, nums, new ArrayList<>(), 0);
return res;
}
/**
*
* @param res 输出的结果集合
* @param nums 原始数组
* @param tmp 临时对象
* @param cur 表示当前位置
*/
private static void dfs(List<List<Integer>> res, Integer[] nums, ArrayList<Integer> tmp, int cur) {
if (nums.length == cur) {
res.add(new ArrayList<>(tmp));
} else {
tmp.add(nums[cur]);
dfs(res, nums, tmp, cur + 1);
tmp.remove(tmp.size() - 1);
dfs(res, nums, tmp, cur + 1);
}
}
输出:
[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
复杂度分析
- 时间复杂度:O(n * 2 ^ n)。一共 2^n个状态,每种状态需要 O(n)的时间来构造子集。
- 空间复杂度:O(n)。临时数组 t 的空间代价是 O(n),递归时栈空间的代价为 O(n)。
解题思路三: 常规思路,非递归
思路与算法
对于例子[1,2,3]来说,最开始是空集,那么我们现在要处理1,就在空集上加1,为[1]。
现在我们有两个自己[]和[1],下面我们来处理2,我们在之前的子集基础上,每个都加个2,可以分别得到[2],[1, 2]。那么现在所有的子集合为[], [1], [2], [1, 2]。
同理处理3的情况可得[3], [1, 3], [2, 3], [1, 2, 3], 再加上之前的子集就是所有的子集合了。
代码实现
public static List<List<Integer>> method1(Integer[] nums) {
// 子集列表
List<List<Integer>> res = new ArrayList<>();
// 空集
res.add(new ArrayList<>());
if(nums==null||nums.length==0){
return res;
}
// 非空集
for(int i=0; i< nums.length; i++){
// 目前已经存在的子集数量
int size = res.size();
for(int j=0; j<size; j++){
// 取得该具体的子集
List<Integer> cur=new ArrayList<>(res.get(j));
// 子集中追加 i
cur.add(nums[i]);
// 追加后的列表作为新子集
res.add(new ArrayList<>(cur));
}
}
return res;
}
输出
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
解题思路四: 回溯法动态规划
代码实现
public static List<List<Integer>> method3(Integer[] nums) {
// 子集列表
List<List<Integer>> res = new ArrayList<>();
backtrack(res, nums, new ArrayList<>(), 0);
return res;
}
private static void backtrack(List<List<Integer>> res, Integer[] nums, ArrayList<Integer> tmp, int start) {
//走过的所有路径都是子集的一部分,所以都要加入到集合中
res.add(new ArrayList<>(tmp));
for(int i = start; i < nums.length; i++){
//做出选择
tmp.add(nums[i]);
//递归
backtrack(res, nums, tmp, i + 1);
//撤销选择
tmp.remove(tmp.size() - 1);
}
}
输出:
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
~ end