Power Set

The problem, simply

You get a list of n different items. Give back every subset: every group you can make by picking some of the items, in any amount from none to all. The empty group counts, and so does the whole list.

With n items there are 2^n subsets, because each item is either in or out. Space for the answer does not count as extra room below.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk through the items one by one and make a choice for each: leave it out, or put it in. Each choice splits the work into two branches, so the choices form a tree. Every leaf at the bottom is one finished subset.

1. Start with an empty bag at item 0.
2. Branch one: skip the item and go to the next.
3. Branch two: put the item in, go to the next, then take it back out.
4. When all items are decided, copy the bag into the answer.

import java.util.*;

class Solution {
    public static List<List<Integer>> powerSet(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        choose(nums, 0, new ArrayList<>(), out);
        return out;
    }

    private static void choose(int[] nums, int i, List<Integer> bag, List<List<Integer>> out) {
        if (i == nums.length) {
            out.add(new ArrayList<>(bag));      // every item decided: save a copy
            return;
        }
        choose(nums, i + 1, bag, out);          // leave nums[i] out
        bag.add(nums[i]);                       // put nums[i] in
        choose(nums, i + 1, bag, out);
        bag.remove(bag.size() - 1);             // take it back out
    }
}

How long it takes: 2^n leaves, and copying each bag costs up to n, O(n * 2^n). Extra room: the call stack and the bag are n deep, O(n).

Way 2: the clever way

A number from 0 to 2^n - 1 has n bits. Treat each bit as the switch for one item. Every number gives a different pattern of switches, and every pattern shows up once. So counting from 0 to 2^n - 1 lists every subset, with no recursion.

1. Let total = 1 << n, which is 2^n.
2. For each mask from 0 to total - 1, make a new bag.
3. For each j from 0 to n - 1, if bit j of mask is on, put nums[j] in the bag.
4. Add the bag to the answer.

import java.util.*;

class Solution {
    public static List<List<Integer>> powerSet(int[] nums) {
        int n = nums.length;
        List<List<Integer>> out = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> bag = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) {
                    bag.add(nums[j]);           // switch j is up: item j goes in
                }
            }
            out.add(bag);
        }
        return out;
    }
}

How long it takes: 2^n masks, each checking n bits, O(n * 2^n). Extra room besides the answer: the counters, O(1). No call stack at all.

Watch out for

• In Way 1, adding bag itself instead of a copy. All saved bags would be the same list, and they end up empty after backtracking.
• Checking bit j with (mask & (1 << j)) == 1. That is only right for j = 0. Use != 0, or ((mask >> j) & 1) == 1.
• Forgetting the empty subset, or returning an empty list for empty input instead of a list with one empty list.

What interviewers ask next

• The items have repeats, like [1, 2, 2]? Sort first. In the choice tree, after skipping a value, skip all its copies too, so [1, 2] is not made twice.
• Only subsets of size k? Use the choice tree and stop a branch when the bag is full, or loop masks and keep those with Integer.bitCount(mask) == k.
• Visit subsets so that each one differs from the last by one item? Use Gray code: mask i ^ (i >> 1).
• Another simple way? Start with [[]]. For each item, copy every bag you have and add the item to the copies. That doubles the list each time.
• Loop over all subsets of a given mask m? for (int s = m; s > 0; s = (s - 1) & m), a classic in bitmask DP.

Remember this

Grown-up words: the bag is a subset, the list of all bags is the power set, the light switches are a bitmask, and the skip or take tree is backtracking.