☕ DSA Java Articles

Topics › Bit Manipulation › Interview Problems

Power Set Bit Manipulation

Medium TUF ID 142 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array nums of n distinct integers. Return its power set: every possible subset, including the empty set and the full set, in any order. There are exactly 2^n of them. The TUF statement gives a string instead of an array and asks for all of its subsequences; it is the same problem, since a subsequence is just a subset of positions, and the Java file includes that version too.

Constraints: 0 ≤ n ≤ 16 (the output alone has 2^n entries, so n is always small), values fit in a 32-bit signed integer and are pairwise distinct.

Example 1

nums = [1, 2, 3]
answer = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]   // 2^3 = 8 subsets

Example 2

nums = [5]
answer = [[], [5]]

Example 3

nums = []
answer = [[]]          // the empty set has exactly one subset: itself

Approach 1: Recursion, take or skip each element

Intuition. Build a subset one decision at a time. Standing at index index, there are only two things to do with nums[index]: leave it out or put it in. Make both choices recursively; when index reaches n, every element has been decided and the current list is one complete subset. Because every element has exactly two options and the choices are independent, the recursion tree has exactly 2^n leaves, one per subset, and no subset is produced twice.

Algorithm.

  1. Start with index = 0 and an empty current list.
  2. If index == n, copy current into the result and return.
  3. Recurse with index + 1 without adding nums[index] (skip).
  4. Append nums[index], recurse with index + 1 (take), then remove it again so the caller sees current unchanged (backtracking).
static List<List<Integer>> recursion(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    buildSubsets(nums, 0, new ArrayList<>(), result);
    return result;
}

private static void buildSubsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) {
    if (index == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    buildSubsets(nums, index + 1, current, result);        // skip nums[index]
    current.add(nums[index]);                              // take nums[index]
    buildSubsets(nums, index + 1, current, result);
    current.remove(current.size() - 1);                    // undo the choice before returning
}

Complexity. Time O(2^n × n): there are 2^n leaves and copying a subset costs up to n. Space O(n) for the recursion stack and the shared current list, not counting the output.

Two details matter. The copy new ArrayList<>(current) is essential; adding current itself would put the same mutable list into the result 2^n times. And current.remove(current.size() - 1) calls the remove(int index) overload, which is what we want; remove(Integer.valueOf(x)) would search by value and be both slower and wrong if values could repeat.

This approach is perfectly fine and generalises to combinations, permutations and pruning. Its only drawbacks are recursion overhead and the fact that the order of the output depends on the traversal.

Approach 2: Optimal, enumerate bitmasks

Intuition. A subset of n elements is a yes/no decision for each position: n bits. An n-bit number is such a sequence of decisions. So the integers 0, 1, 2, ..., 2^n - 1 are in one-to-one correspondence with the subsets: read bit i of the mask as “is nums[i] included?”. Enumerating all subsets becomes a plain counting loop, and extracting a subset becomes testing n bits. There is no recursion, no backtracking state and the output order is fixed and predictable.

Algorithm.

  1. Let total = 1 << n (that is 2^n).
  2. For every mask from 0 to total - 1:
  3. For every position i from 0 to n - 1, if bit i of mask is set ((mask & (1 << i)) != 0), append nums[i] to the current subset.
  4. Add the subset to the result.
static List<List<Integer>> optimal(int[] nums) {
    int n = nums.length;
    int total = 1 << n;                                    // 2^n subsets
    List<List<Integer>> result = new ArrayList<>(total);
    for (int mask = 0; mask < total; mask++) {
        List<Integer> subset = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) subset.add(nums[i]);
        }
        result.add(subset);
    }
    return result;
}

Dry run on nums = [1, 2, 3]:

mask binary (bit2 bit1 bit0) included positions subset
0 000 none []
1 001 0 [1]
2 010 1 [2]
3 011 0, 1 [1, 2]
4 100 2 [3]
5 101 0, 2 [1, 3]
6 110 1, 2 [2, 3]
7 111 0, 1, 2 [1, 2, 3]

Every subset appears exactly once because every integer in [0, 2^n) has exactly one binary representation.

Complexity. Time O(2^n × n): 2^n masks, each tested against n bits. Space O(1) beyond the output. The asymptotics match the recursion, but the constant is smaller and the loop is trivially iterative.

Why (mask & (1 << i)) != 0 rather than == 1? mask & (1 << i) is either 0 or 1 << i, not 0 or 1. Comparing against 1 would only ever be true for i = 0. The alternative ((mask >> i) & 1) == 1 shifts the bit down first, and that can be compared with 1. Both forms are used in the Java file.

The string version

The TUF statement hands you a string s and asks for all subsequences. Nothing changes except that a StringBuilder collects the chosen characters:

static List<String> subsequences(String s) {
    int n = s.length();
    List<String> result = new ArrayList<>();
    for (int mask = 0; mask < (1 << n); mask++) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (((mask >> i) & 1) == 1) sb.append(s.charAt(i));
        }
        result.add(sb.toString());
    }
    return result;
}

For s = "abc" this yields "", "a", "b", "ab", "c", "ac", "bc", "abc" in mask order. If the string has repeated characters, such as "aa", the output contains "a" twice because the two occurrences come from different positions; de-duplicate with a Set if the problem wants distinct strings.

Edge cases and pitfalls