给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
题目标签:Bit Manipulation / Array / Backtracking
题目链接:LeetCode / LeetCode中国
递归就像机器人造小机器人帮自己干活,注意递归终止条件。
Language | Runtime | Memory |
---|---|---|
cpp | 4 ms | N/A |
class Solution {
private:
void robot(int idx, vector<int>& nums, vector<vector<int>>& res, vector<bool>& mask){
if(idx >= nums.size()){
vector<int> r;
for(int i=0; i<nums.size(); i++){
if(mask[i]){
r.push_back(nums[i]);
}
}
res.push_back(r);
}else{
mask[idx] = true;
robot(idx + 1, nums, res, mask);
mask[idx] = false;
robot(idx + 1, nums, res, mask);
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<bool> mask;
for(int i : nums){
mask.push_back(false);
}
robot(0, nums, res, mask);
return res;
}
};
Language | Runtime | Memory |
---|---|---|
python3 | 56 ms | N/A |
class Solution:
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
for i in range(2 ** len(nums)):
mask = bin(i)[2:].rjust(len(nums), '0')
res.append([n for j, n in enumerate(nums) if mask[j] == '1'])
return res