78. Subsets

Problem

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

Note: The solution set must not contain duplicate subsets.

Example:

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

Discussion

The problem requires all possible subsets given a distinct set of integers. We know the size of the answer would be of size 2 ^ n for subset problem.

Further more, we can consider the subset solutions to be different combination of each element in the input set. Consider the example with input [1, 2, 3]:

We can see the result is a set of combination of switching on/off of each element in the input list. And we can map the combination into binary string, then decimal integers below n.

Thus we can solve the problem by mapping all those integers into different subsets.

Solution

Given input with size n, we have result with size 2 ^ n. For all integers in [0, 2^n), we can change it to binary string format, and thus integer combination of set integers, and finally different subsets.

The most difficult part is converting integer to binary string. Simply apply bin(i) will yield binary string 0b***** from integer i.

Yet to allow binary string carrying all n digits, we should add leading 0s for small integers. Achieving this we add n to every integer i, so every binary string will be 0b1*****. Omitting the first 3 characters and we can extract the binary form string.

Thus viewing the binary form string as a list of index respect to the input list, we can obtain the corresponding subset.

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        length = len(nums)
        size = 2 ** length

        for i in range(size):
            binary = bin(i | size)[3:]
            result.append([
                nums[j]
                for j in range(length)
                if binary[j] == '1'
            ])

        return result

Complexity Analysis

• Time Complexity: O(n * 2 ^ n), considering the solution set of size 2 ^ n, with each subset have at most n elements
• Space Complexity: O(n * 2 ^ n), considering the solution set of size 2 ^ n, with each subset have at most n elements