Subsets

Introduction

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.

Solutions

1. Using DFS

This solution is straightforward. Starting from an empty list, it appends elements recursively to build all possible subsets of the given list nums.

def subsets(nums: List[int]) -> List[List[int]]:
    answer = []

    def dfs(lst, index=0):
        answer.append(lst)
        if index == len(nums):
            return
        for i in range(index, len(nums)):
            dfs(lst + [nums[i]], i + 1)

    dfs([], 0)

    return answer

References

• Leetcode Subsets Problem
• 파이썬 알고리즘 인터뷰(Python Algorithm Interview)