LeetCode 78. Subsets



Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]


  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.


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(results, nums, [], 0)
        return results
    def helper(self, results, nums, subset, start):
        for i in range(start, len(nums)):
            num = nums[i]
            self.helper(results, nums, 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 *