LeetCode 78. Subsets

Description

https://leetcode.com/problems/subsets/

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

Explanation

The problem is a typical depth first search coding problem.

We can have a recursion function to add visited subsets to the final results. Remember to make a deep copy when we need to add subset to the results.

Java Solution

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        
        if (nums == null || nums.length == 0) {
            return results;
        }
        
        Arrays.sort(nums);
        
        List<Integer> subset = new ArrayList<>();
        toFindAllSubsets(nums, results, subset, 0);                
        
        return results;
    }
    
    private void toFindAllSubsets(int[] nums, List<List<Integer>> results, List<Integer> subset, int startIndex) {
        results.add(new ArrayList<>(subset));
        
        for (int i = startIndex; i < nums.length; i++) {
            subset.add(nums[i]);
            toFindAllSubsets(nums, results, subset, i + 1);
            subset.remove(subset.size() - 1);            
        }        
    }
}

Python Solution

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        
        nums = list(sorted(nums))
        self.helper(nums, 0, [], result)
        
        return result
    
    def helper(self, nums, start_index, subset, result):

        result.append(list(subset))        
        
        for i in range(start_index, len(nums)):
            subset.append(nums[i])
            
            self.helper(nums, i + 1, subset, result)
            
            subset.pop()
  • Time complexity: \mathcal{O}(N \times 2^N)O(N×2N) to generate all subsets and then copy them into output list.
  • Space complexity: \mathcal{O}(N \times 2^N)O(N×2N) to keep all the subsets of length NN, since each of NN elements could be present or absent.
  • Time complexity: O(N×2^N) to generate all subsets and then copy them into the output list.
  • Space complexity: O(N×2^N) to keep all the subsets of length N, since each of N elements could be present or absent.

2 Thoughts to “LeetCode 78. Subsets”

Leave a Reply

Your email address will not be published. Required fields are marked *