面试题 08.04

Write a method to return all subsets of a set. The elements in a set are pairwise distinct.

Note: The result set should not contain duplicated subsets.

Example:

Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

Solutions

• The same as problem 78

• dfs

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void dfs(vector<int> & nums, int st) {
        if (st >= nums.size())
            res.push_back(path);
        else {
            path.push_back(nums[st]);
            dfs(nums, st + 1);
            path.pop_back();
            dfs(nums, st + 1);
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }
};

• python version

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:

        return [first + sub 
                for sub in self.subsets(nums[1:]) 
                for first in ([nums[0]], [])] if nums else [[]]