Solutions

1. Backtracking

O(n * 2ⁿ) time | O(n) space

Intuition

We can grow a tree, where each node holds a subset and an index of the last element taken. Every element that comes after the index starts a new branch.

So the root is an empty subset at index 0, with one branch for each element, each holding a subset of that one element.

Algorithm

Create a subsetsFrom function taking the input array, an index, current subset and result for all the subsets.
- Add current to result.
- Iterate through the loop from index to the last element.
- For each element, call subsetsFrom again from the next index, with that element added to current.
Call subsetsFrom with an empty current and an index of 0, and return the result.

012

[]

[2]

[2,5]

[2,5,9]

[2,9]

[5]

[5,9]

[9]

start with [], index: 0

1 / 9

Code

def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    subsetsFrom(nums, 0, [], result)
    return result


def subsetsFrom(nums: list[int], index: int, current: list[int], result: list[list[int]]) -> None:
    result.append(current)
    for i in range(index, len(nums)):
        extended = current + [nums[i]]
        subsetsFrom(nums, i + 1, extended, result)

/**
 * @param {number[]} nums
 * @returns {number[][]}
 */
var subsets = function (nums) {
  const result = []
  subsetsFrom(nums, 0, [], result)
  return result
}

function subsetsFrom(nums, index, current, result) {
  result.push(current)
  for (let i = index; i < nums.length; i++) {
    const extended = [...current, nums[i]]
    subsetsFrom(nums, i + 1, extended, result)
  }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[][] subsets(int[] nums) {
        List<int[]> result = new ArrayList<>();
        subsetsFrom(nums, 0, new int[0], result);
        return result.toArray(new int[0][]);
    }

    private void subsetsFrom(int[] nums, int index, int[] current, List<int[]> result) {
        result.add(current);
        for (int i = index; i < nums.length; i++) {
            int[] extended = Arrays.copyOf(current, current.length + 1);
            extended[current.length] = nums[i];
            subsetsFrom(nums, i + 1, extended, result);
        }
    }
}

2. Bit Mask

O(n * 2ⁿ) time | O(1) space

Intuition

There are 2ⁿ subsets in the array of size n, and we can represent each subset as a bitmask where each bit tells if the element at this index is included in the subset.

So counting from 0 up to 2ⁿ reaches every subset once.

012

number	bitmask	subset
0	[0,0,0]	[]
1	[1,0,0]	[2]
2	[0,1,0]	[5]
3	[1,1,0]	[2,5]
4	[0,0,1]	[9]
5	[1,0,1]	[2,9]
6	[0,1,1]	[5,9]
7	[1,1,1]	[2,5,9]

Algorithm

Iterate through the outer loop while the number is less than 2ⁿ, treating each number as a mask.
For each outer loop iteration, create an empty current subset and iterate through the inner loop from the first element to the last element with i index.
Add the element at i to current when bit i of the mask is 1.
Add current to result when the inner loop finishes.
Return the result.

012

bitmask: [0,0,0], 2 is skipped, subset: []

1 / 25

Code

def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    for mask in range(1 << len(nums)):
        current = []
        for i in range(len(nums)):
            if mask >> i & 1:
                current.append(nums[i])
        result.append(current)
    return result

/**
 * @param {number[]} nums
 * @returns {number[][]}
 */
var subsets = function (nums) {
  const result = []
  for (let mask = 0; mask < 1 << nums.length; mask++) {
    const current = []
    for (let i = 0; i < nums.length; i++) {
      if ((mask >> i) & 1) {
        current.push(nums[i])
      }
    }
    result.push(current)
  }
  return result
}

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] subsets(int[] nums) {
        List<int[]> result = new ArrayList<>();
        for (int mask = 0; mask < 1 << nums.length; mask++) {
            int[] current = new int[Integer.bitCount(mask)];
            int at = 0;
            for (int i = 0; i < nums.length; i++) {
                if ((mask >> i & 1) == 1) current[at++] = nums[i];
            }
            result.add(current);
        }
        return result.toArray(new int[0][]);
    }
}