AlgoPressAppearance
0078-子集
https://leetcode.cn/problems/subsets
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- nums 中的所有元素 互不相同
思路：递归
类似于组合，每次选取一个数字加入列表，因为不能包含重复的子集，所以需要排序 前面组合过的数字不能再次出现
注意：
- 组合问题是排序的，所以 for 就要从 startIndex 开始，而不是从 0 开始!
- 如果是排列问题，for 循环就从 0 开始
参考代码
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
private void dfs(int[] nums, int begin, List<int> list){
//因为要收集所有子集情况，所以直接加入result，包括最开始的空集
result.Add(new List<int>(list.ToArray()));
for(int i=begin; i < nums.Length; i++){
list.Add(nums[i]);
dfs(nums,i+1,list);
list.RemoveAt(list.Count-1);
}
}
public IList<IList<int>> Subsets(int[] nums) {
List<int> list = new List<int>();
dfs(nums,0,list);
return result;
}
}
思路2：迭代法【官方】
比如有3位数字的时候， 我们将这三位数用二进制表示，那么 000 表示每个数字都没选， 111 表示每个数字都选了。 哪个数字为1，就表示哪个数组选了，这样遍历出所有情况就是所有的子集。
例如，n = 3 ，a = { 5, 2, 9 } 时：
| 0/1 序列 | 子集 | 0/1序列对应的二进制数 |
|---|---|---|
| 000 | {} | 0 |
| 001 | 1 | |
| 010 | 2 | |
| 011 | 3 | |
| 100 | 4 | |
| 101 | 5 | |
| 110 | 6 | |
| 111 | 7 |
参考代码
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
List<int> list = new List<int>();
public IList<IList<int>> Subsets(int[] nums) {
int n = nums.Length;
int mask = 0;
while(mask < (1 << n)){
list.Clear();
//判断数字是否需要加入
for(int i=0; i<nums.Length; i++){
if( mask & (1 << i) != 0){
list.Add(nums[i]);
}
}
//加入结果值
result.Add(new List<int>(list.ToArray()));
mask ++;
}
return result;
}
}
复习迭代:2022-05-12
csharp
public class Solution {
public IList<IList<int>> Subsets(int[] nums) {
//迭代法
int n = nums.Length;
List<IList<int>> result = new List<IList<int>>();
for(int mask = 0; mask < (1<<n); mask++){
List<int> list = new List<int>();
for(int i=0; i<n; i++){
if( (mask & (1<<i)) != 0){ //此处不能说==1，因为可能结果是 010，或者100
list.Add(nums[i]);
}
}
result.Add(list);
}
return result;
}
}