剑指 Offer II 079. 所有子集｜78. 子集：
给定一个整数数组 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 中的所有元素 互不相同
分析
- 这道算法题用递归我觉得相对比较简单，深度优先，但是二当家的偏不。
- 根据题意，所有子集就是每个数字都可以选择或者不选，取所有的可能组合，都不选也是一个组合，也是一个子集。
- 题目中说不能包含重复题解，这个理所当然。
- 提示中说每个数字各不相同，那我们子集就可以考虑成数字所在位置或者说是数组的下标的不同组合，因为数字都不同，所以我们就不必关心每个数字是几了。
- 每个位置都有两种情况，选择或者不选择，这种熟悉的味道，情况与二进制不能说毫无关系，可以说是一模一样，我们已经可以推算题解的个数就是 2nums.length，也就是
1 << nums.length。 - 提示中还说数字个数最多10个，那我们最多用10个二进制位就可以表示所有数字的选择和不选择，一个 int 型变量足以，我们用这个 int 型变量的二进制位变化，去对应数字的选择和不选择。
题解
java
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
int n = 1 << nums.length;
for (int i = 0; i < n; ++i) {
List<Integer> ansRow = new ArrayList<>();
for (int j = 0; j < nums.length; ++j) {
if (((i >> j) & 1) != 0) {
ansRow.add(nums[j]);
}
}
ans.add(ansRow);
}
return ans;
}
}c
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
int n = 1 << numsSize;
*returnSize = n;
// 结果
int **ans = (int **) malloc(sizeof(int *) * n);
// 每行结果的长度
*returnColumnSizes = (int *) malloc(sizeof(int) * n);
for (int i = 0; i < n; ++i) {
// 这里不满的行都会浪费内存，烦死
ans[i] = (int *) malloc(sizeof(int) * numsSize);
(*returnColumnSizes)[i] = 0;
for (int j = 0; j < numsSize; ++j) {
if ((i >> j) & 1) {
ans[i][(*returnColumnSizes)[i]++] = nums[j];
}
}
}
return ans;
}c++
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
int m = nums.size();
int n = 1 << m;
for (int i = 0; i < n; ++i) {
vector<int> ansRow;
for (int j = 0; j < m; ++j) {
if ((i >> j) & 1) {
ansRow.push_back(nums[j]);
}
}
ans.push_back(ansRow);
}
return ans;
}
};python
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
m = len(nums)
n = 1 << m
ans = []
for i in range(n):
row = []
for j in range(m):
if (i >> j) & 1:
row.append(nums[j])
ans.append(row)
return ans
go
func subsets(nums []int) [][]int {
ans := make([][]int, 0)
m := len(nums)
n := 1 << m
for i := 0; i < n; i++ {
row := make([]int, 0)
for j := 0; j < m; j++ {
if ((i >> j) & 1) != 0 {
row = append(row, nums[j])
}
}
ans = append(ans, row)
}
return ans
}rust
impl Solution {
pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut ans: Vec<Vec<i32>> = Vec::new();
let m = nums.len();
let n = 1 << m;
(0..n).for_each(|i|{
let mut row:Vec<i32> = Vec::new();
nums.iter().enumerate().for_each(|(j, num)| {
if ((i >> j) & 1) != 0 {
row.push(*num);
}
});
ans.push(row);
});
ans
}
}
原题传送门：https://leetcode-cn.com/problems/TVdhkn/
原题传送门：https://leetcode-cn.com/problems/subsets/
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
