78. Subsets - cocoder39/coco39_LC GitHub Wiki

78. Subsets

2020 Notes:

[1, 2, 3]

[] -> 1 -> 1,2 -> 1,2,3 
        -> 1,3
   -> 2 -> 2,3
   -> 3

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.helper(nums, 0, [], res)
        return res
        
    
    def helper(self, nums, cur_idx, path, res):
        res.append(path[:])
        
        for i in range(cur_idx, len(nums)):
            path.append(nums[i])
            self.helper(nums, i+1, path, res)
            path.pop()
  • Time complexity: There are 2^N solutions since each number can be absent or present in a result. Each invocation of helper() adds one result to result list so there are 2^N invocations of helper(). Each helper() copies one result to result list so the total complexity is O(N * 2^N)
  • Space complexity: O(N * 2^N) to store all results and O(N) to store recursion stack so O(N * 2^N) intatal

Compared with solution below, this approach can be easily extended to support SubsetsII

==================================================================================================

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        helper(res, cur, nums, 0);
        return res;
    }
private:
    void helper(vector<vector<int>>& res, vector<int>& cur, vector<int>& nums, int start) {
        if (start == nums.size()) {
            res.push_back(cur);
            return;
        }
        
        helper(res, cur, nums, start + 1);
        cur.push_back(nums[start]);
        helper(res, cur, nums, start + 1);
        cur.pop_back();
    }
};
⚠️ **GitHub.com Fallback** ⚠️