LeetCode 78. Subsets



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

Note: The solution set must not contain duplicate subsets.


Input: nums = [1,2,3]


The problem is a typical backtracking coding problem. We can have a recursion helper function to add visited subsets to the final results. Remember to make a deep copy when we are adding a 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;
        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++) {
            toFindAllSubsets(nums, results, subset, i + 1);
            subset.remove(subset.size() - 1);            

Python Solution

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        results = []
        self.helper(nums, results, [], 0)    
        return results
    def helper(self, nums, results, subset, start):
        for i in range(start, len(nums)):
            self.helper(nums, results, subset, i + 1)
  • Time complexity: O(N * 2^N) to generate all subsets and then copy them into the output list. The number for ecursive calls T(n) satisfies the recurrence T(n) = T(n-1) + T(n-2) + T(1) + T(0), which solves to T(n) = O(2^n) .Since we spend O(n) time within a call , the time complexity is O(N * 2^N).
  • 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 *