题目描述
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
样例
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
输入:nums = [0]
输出:[[],[0]]
算法1
(DFS + 回溯) $O(n * 2^n)$
做这题之前强烈建议先做LeetCode 的46,47 题再来做这题.
时间复杂度
上面的代码中,dfs(cur,n) 参数表示当前位置是 cur,原序列总长度为 n。原序列的每个位置在答案序列中的状态有被选中和不被选中两种,我们用 t 数组存放已经被选出的数字。在进入 dfs(cur,n)之前 [0,cur−1] 位置的状态是确定的,而 [cur,n−1] 内位置的状态是不确定的,dfs(cur,n) 需要确定 cur 位置的状态,然后求解子问题 dfs(cur+1,n)。对于 cur 位置,我们需要考虑 a[cur] 取或者不取,如果取,我们需要把 a[cur] 放入一个临时的答案数组中(即上面代码中的 t),再执行 dfs(cur+1,n),执行结束后需要对 t 进行回溯;如果不取,则直接执行 dfs(cur+1,n)。在整个递归调用的过程中,cur 是从小到大递增的,当 cur增加到 n 的时候,记录答案并终止递归。可以看出二进制枚举的时间复杂度是 O(2n)。
总结:当一个数有选和不选两种状态时: O(2^n)
整体时间复杂度: O(n * 2^n),一共有2^n 种状态,每种状态需要O(n) 的时间来构造子集
参考文献
https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode-solution/
Java 代码
public class 子集 {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp;
public List<List<Integer>> subsets(int[] nums) {
if(nums.length == 0) return res;
temp = new ArrayList<>();
dfs(0,nums);
return res;
}
void dfs(int index,int[] nums){
//这里要求返回的答案其实也是排列问题,只不过不是要求排列到nums.length 的时候才返回答案
//而是每一次组合好的数据都是答案,但是答案之间不能重复: [1,2] [2,1] 是同一个答案
//所以每一此递归都需要把tmp 的值加入到res 中
res.add(new ArrayList<>(temp));
//如果保证组合的答案不会重复? 只需要保证每一次组合数据的时候,不让数据往回组合就行了
//所以这里就和题目<<全排列>> 开始不一样了,全排列的每一次递归中,每次都会从头开始遍历数组
//而这里中,就得从index(当前递归方法的nums[i] 索引,也是递归的深度) 开始组合
for(int i = index; i < nums.length; i++){
temp.add(nums[i]);
dfs(i+1,nums);
//回溯
temp.remove(temp.size()-1);
//nums[1,2,3]
//进入dfs: index == 0, res[[]] , temp:[1]
//进入第一次递归: index == 1, res[[],[1]] temp:[1,2]
//进入到第二次递归:index == 2 res[[],[1],[1,2]] temp[1,2,3]
//进入到第三次递归: index == 3, res[[],[1],[1,2],[1,2,3]] 因为index == nums.length 所以无法进入for 循环,结束此次方法
//回到第二次递归: index == 2, 执行回溯:temp[1,2] 因为此时 i == nums.length - 1,所以dfs方法执行完毕,退出此次dfs(...)
//回到第一次递归: index == 1, 执行回溯: temp[1], 此时i == 1,进入下一次for 循环, i == 2, temp [1,3], index = 2+1 = 3
//进入第二次递归: index == 3, res[[],[1],[1,2],[1,2,3],[1,3]] temp[1,3], 因为此时index == 3 == nums.length,所以无法进入for 循环
//退出此次dfs(...)
//回到第一次递归: index == 1, 执行回溯: temp[1]
//回到递归的开头: index == 0. 执行回溯: temp[] ; 执行下一轮循环: i == 2,此时temp[2]... 然后步骤流程和上面的一样
}
}
}