Generate All Subsets

Given an array of distinct integers, return all of its subsets (the power set). A set of n elements has 2ⁿ subsets, including the empty set and the set itself.

LeetCode: 78. Subsets

Example

Text

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

Bitmasks

Each subset corresponds to an n-bit number: bit i says whether nums[i] is included. Counting from 0 to 2ⁿ - 1 visits every subset exactly once.

Java

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

public class Main {
    static List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> out = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) subset.add(nums[i]);
            }
            out.add(subset);
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1, 2, 3}));
    }
}

Output

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

Time: O(n · 2ⁿ): 2ⁿ masks, each checked bit by bit. Space: O(n · 2ⁿ) for the output.

This is already as fast as possible, because the output itself has n · 2ⁿ / 2 elements in total. But the order follows binary counting, and an int mask limits it to 30 elements: 1 << 31 is negative, so the loop would not run (30 elements would already be a billion subsets).

Backtracking: choose the next element

Build subsets recursively. At each step, the current subset is itself an answer; then try extending it with each element after the last one used, and undo the choice afterwards. Starting after the last used element means no subset is produced twice. With sorted input, the subsets come out in lexicographic order.

Java

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

public class Main {
    static void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> out) {
        out.add(new ArrayList<>(current)); // copy: current keeps changing
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            backtrack(nums, i + 1, current, out);
            current.remove(current.size() - 1);
        }
    }

    static List<List<Integer>> subsets(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        List<List<Integer>> out = new ArrayList<>();
        backtrack(sorted, 0, new ArrayList<>(), out);
        return out;
    }

    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1, 2, 3}));
        System.out.println(subsets(new int[]{3, 1}));
        System.out.println(subsets(new int[]{}));
    }
}

Output

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

Time: O(n · 2ⁿ). Space: O(n) for the recursion and current, besides the output.

Edge cases

Empty input: one subset, the empty one.
Duplicates in the input (LeetCode 90): sort, and in the loop skip nums[i] when i > start && nums[i] == nums[i - 1], so the same value isn't chosen twice at the same position.