Subsets

NeetCode: Subsets · LeetCode: 78. Subsets · Difficulty: Medium

Given an integer array nums of unique elements, return all possible subsets (the power set). The result must not contain duplicate subsets and may be in any order.

Example

Text

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

Brute force: bitmask over 2^n masks

An array of n items has exactly 2^n subsets, and each subset corresponds to one n-bit number: bit i says whether nums[i] is included. Count from 0 to 2^n - 1 and build a subset from each mask. The running time already matches the output size (n · 2^(n-1) numbers in total). The mask limits n to the width of the integer type (here n <= 10, well within a 32-bit int; 1 << n would overflow for n >= 31), and the method does not extend to problems where choices constrain each other.

LeetCode's Java signature returns List<List<Integer>>. main sorts the subsets with a comparator helper so the printed order is fixed.

Java

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

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

    static int cmp(List<Integer> a, List<Integer> b) {
        for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
            int x = a.get(i), y = b.get(i);
            if (x != y) {
                return Integer.compare(x, y);
            }
        }
        return Integer.compare(a.size(), b.size());
    }

    static List<List<Integer>> sorted(List<List<Integer>> lists) {
        List<List<Integer>> copy = new ArrayList<>(lists);
        copy.sort(Main::cmp);
        return copy;
    }

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

Output

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

mask >> i & 1 parses as (mask >> i) & 1 because shifts bind tighter than &, and the comparison with 1 needs the extra parentheses. Time: O(n · 2^n). Space: O(n) besides the output.

Optimal: backtracking decision tree

Walk the array left to right and make one decision per element: include it or skip it. Each root-to-leaf path in this binary tree is one subset, and there are 2^n leaves. Backtracking keeps one shared current list: add the element, recurse, then remove it to undo the choice before trying the other branch. Only copies of current made at the leaves are stored.

Java

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

public class Main {
    static class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            dfs(0, nums, new ArrayList<>(), result);
            return result;
        }

        private void dfs(int i, int[] nums, List<Integer> current, List<List<Integer>> result) {
            if (i == nums.length) {
                result.add(new ArrayList<>(current));
                return;
            }
            // Choice 1: include nums[i].
            current.add(nums[i]);
            dfs(i + 1, nums, current, result);
            current.remove(current.size() - 1); // undo
            // Choice 2: skip nums[i].
            dfs(i + 1, nums, current, result);
        }
    }

    static int cmp(List<Integer> a, List<Integer> b) {
        for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
            int x = a.get(i), y = b.get(i);
            if (x != y) {
                return Integer.compare(x, y);
            }
        }
        return Integer.compare(a.size(), b.size());
    }

    static List<List<Integer>> sorted(List<List<Integer>> lists) {
        List<List<Integer>> copy = new ArrayList<>(lists);
        copy.sort(Main::cmp);
        return copy;
    }

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

Output

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

Time: O(n · 2^n) (2^n leaves, each copying up to n items). Space: O(n) recursion depth besides the output.

Both approaches have the same complexity. The decision tree is the template for the rest of the category: make a choice, recurse, undo the choice, with extra rules that prune branches.