LeetCode 78. Subsets

Link

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

Problem

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

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]]

Solution

• First, create a variable subsets, initialized to [[]], as the return value.
• Loop through nums, and for each element, create new subsets by appending that element to each existing subset.
• Then, append these new subsets to subsets.

Sample code

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        """
        0: [[]]
        1: [[]]+[1] -> [[], [1]]
        2: [[],[1]] + [2],[1,2] -> [[], [1], [2], [1, 2]]
        3: [[], [1], [2], [1, 2]] + [3], [1, 3], [2, 3], [1,2,3] -> [[], [1], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

        """
        subsets = [[]]
        for num in nums:
            new_subsets = [subset + [num] for subset in subsets]
            subsets += new_subsets
        return subsets