给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
题解
第一想法是按长度枚举,不过后来发现没办法列出所有情况,看了下官方题解才知道可以按照二进制枚举。
方法一:迭代法实现子集枚举
0/1 序列 | 子集 | 0/1 序列对应的二进制数 |
---|---|---|
000 | {} | 0 |
001 | {9} | 1 |
010 | {2} | 2 |
011 | {2,9} | 3 |
100 | {5} | 4 |
101 | {5,9} | 5 |
110 | {5,2} | 6 |
111 | {5,2,9} | 7 |
复杂度分析:
- 时间复杂度: O(n \times 2^n)
一共 2^n 个状态,每种状态需要 O(n) 的时间来构造子集。 - 空间复杂度: O(n)
即构造子集使用的临时数组的空间代价。
迭代
class Solution {
fun subsets(nums: IntArray): List<List<Int>> {
val ans = mutableListOf<List<Int>>()
val len = nums.size
for (i in 0..1.shl(len)-1) { //0~2^n-1
val list = mutableListOf<Int>()
for (j in 0..len-1) { //每一位
if (i.and(1.shl(j)) != 0) // &位运算,获取每一位不为0的数
list.add(nums[j])
}
ans.add(list)
}
return ans
}
}
方法二:递归法实现子集枚举
复杂度分析
- 时间复杂度:O(n \times 2^n)
一共 2^n 个状态,每种状态需要 O(n) 的时间来构造子集。 - 空间复杂度:O(n)
临时数组的空间代价是O(n),递归时栈空间的代价为O(n)。
递归
class Solution {
val ans = mutableListOf<List<Int>>()
val list = mutableListOf<Int>()
fun subsets(nums: IntArray): List<List<Int>> {
dfs(0,nums)
return ans
}
fun dfs(cur:Int, nums: IntArray){
if (cur==nums.size){
val tmp = list.toList()
ans.add(tmp)
return
}
list.add(nums[cur])
dfs(cur+1,nums)
list.removeAt(list.size-1)
dfs(cur+1,nums)
}
}
Comments | 1 comment
快递单号网,真实物流信息,一单一号,超级单号网www.chaojidanhao.cn