Sweaty Imposter

Subsets

MediumSubsets (BFS-style generation)NeetCode 150MidOpen on LeetCodeUpdated

You're given an array nums of distinct integers. Return every possible subset, including the empty set and nums itself, for 2^n subsets in total. A subset is any selection of the elements, and order inside it doesn't matter, so [1,2] and [2,1] are the same subset and only one may appear. The subsets, and the values within each, can be returned in any order.

Examples

nums = [1,2,3] returns [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Each of the 3 numbers is either in or out of a subset, so there are 2^3 = 8 subsets: the empty set, three single numbers, three pairs and the full set.

nums = [0] returns [[],[0]]

One number gives 2 subsets: one without it ([]) and one with it ([0]).

Constraints

  • 1 <= nums.length <= 10
  • All numbers distinct.

Hints

Hint 1

How does the set of subsets change when you add one more element to the input?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Build the answer one number at a time. Start with a list holding only the empty subset. For each number, copy every subset already in the list, add the number to each copy, and append the copies, so the count doubles and every in-or-out choice appears exactly once. O(n * 2^n) time and space, since there are 2^n subsets of up to n elements each.

Time

O(n * 2^n)

Space

O(n * 2^n)

Pitfall

Adding the number to the existing subset lists instead of to copies, which changes subsets already in the result. Also take the result's size before the inner loop, since looping over a list you keep appending to never ends.

Solutions

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for (int num : nums) {
            int size = result.size();
            for (int i = 0; i < size; i++) {
                List<Integer> subset = new ArrayList<>(result.get(i));
                subset.add(num);
                result.add(subset);
            }
        }
        return result;
    }
}
Drill This