题目
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例1
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例2
输入:nums = [0]
输出:[[],[0]]
思路
这个题最直观的方法就是用递归去实现。数组的每一个数字都可以选择是否拿取。
还有一个比较巧妙的方法,就是用二进制来代表数组的每一个位置是否拿取。比如数组一共有三个数字,000代表每个数字都不拿取,001代表只拿最后一个,010代表只拿第二个。我们可以发现0 ~ 7就可以代表所有拿取方法的可能性。所以遍历的时候只需要遍历0 ~ 7,然后根据数字去判断拿取哪几个元素即可。
代码
递归
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class Solution {
List<List<Integer>> result = new ArrayList<>();
Stack<Integer> cache = new Stack<>();
public List<List<Integer>> subsets(int[] nums) {
dfs(nums, 0);
return result;
}
public void dfs(int[] nums, int index) {
if (index == nums.length) {
result.add(new ArrayList<>(cache));
return;
}
dfs(nums, index+1);
cache.push(nums[index]);
dfs(nums, index+1);
cache.pop();
}
}
时间复杂度:O(n * 2^n)。一共(2 ^ n)个状态,每种状态需要 O(n)的时间来构造子集。
空间复杂度:O(n)。即构造子集使用的临时数组的空间代价。
二进制迭代法
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> cache = new ArrayList<>();
for (int mask = 0; mask < (1 << nums.length); mask++) {
cache.clear();
for (int i = 0; i < nums.length; i++) {
if ((mask & (1 << i)) != 0) {
cache.add(nums[i]);
}
}
result.add(new ArrayList<>(cache));
}
return result;
}
}
时间复杂度和空间复杂度同递归法
总结
二进制迭代法是一个很有意思的方法,这个题目是一个非常合适的使用场景。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)