Subsets — LeetCode 78 Python Solution

The problem

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Example

Input

nums = [1,2,3]

Output

[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Python solution

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(i: int):
            if i == len(nums):
                ans.append(t[:])
                return
            dfs(i + 1)
            t.append(nums[i])
            dfs(i + 1)
            t.pop()

        ans = []
        t = []
        dfs(0)
        return ans

Complexity

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 78. Subsets is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems