78-subsets.md

78. Subsets - 子集

给定一组不含重复元素的整数数组 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