☕ DSA Java Articles

Topics › Recursion and Backtracking › Subsequences Pattern

Power Set

Medium TUF ID 878 A2Z

Java source ↗ Edit this article ↗

Problem

Given a string s, return its power set: every subsequence of s, where a subsequence keeps the original relative order of the characters but may skip any of them. For n characters there are exactly 2^n subsequences (each character is either in or out), including the empty string and s itself.

The GeeksforGeeks version asks for the non-empty subsequences in lexicographic order; the methods below generate all 2^n and a small wrapper produces that exact output. LeetCode’s “Subsets” is the same problem on an integer array.

Constraints: 1 ≤ n ≤ 16 or so; the output has 2^n strings, so the input cannot be large.

Example 1

s = "abc"
answer = ["", "a", "ab", "abc", "ac", "b", "bc", "c"]      // 2^3 = 8, shown sorted

Example 2

s = "ba"
answer = ["", "a", "b", "ba"]      // "ab" is not a subsequence: order must be preserved

Every method returns the same multiset of strings; they differ in the order they produce them, which the article points out because each order is useful somewhere.

Approach 1: Bit masking

Intuition. A subsequence is a yes/no decision per character, so it is an n-bit number: bit i set means “take s[i]”. The numbers 0 .. 2^n - 1 enumerate every combination of decisions exactly once. For each number, walk the bits and append the chosen characters in index order, which keeps them in the original relative order.

Algorithm.

  1. For mask = 0 .. 2^n - 1:
  2. For i = 0 .. n - 1, if bit i of mask is set, append s[i] to a builder.
  3. Add the builder’s string to the result.
static List<String> bitmask(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 & (1 << i)) != 0) sb.append(s.charAt(i));   // bit i set: take s[i]
        }
        result.add(sb.toString());
    }
    return result;
}

Dry run on "abc":

mask binary (c b a) subsequence
0 000 ""
1 001 "a"
2 010 "b"
3 011 "ab"
4 100 "c"
5 101 "ac"
6 110 "bc"
7 111 "abc"

Complexity. Time O(2^n · n): 2^n masks, n bits each. Space O(n) besides the output. There is no recursion, so no stack concerns; the limit is 1 << n, which must stay inside an int (n ≤ 30).

Approach 2: Optimal, take / not-take recursion

Intuition. This is the recursion the whole “subsequences” section of the sheet is built on. Walk an index through the string. At each index make one of two choices, take s[index] into the current subsequence or leave it out, and recurse to index + 1. When the index reaches n, a decision has been made for every character and the current builder holds one complete subsequence. Two choices at each of n levels gives 2^n leaves, one per subsequence.

Algorithm.

  1. generate(index, current): if index == n, record current and return.
  2. Append s[index], recurse on index + 1, then remove the appended character (undo).
  3. Recurse on index + 1 without appending.
static List<String> recursive(String s) {
    List<String> result = new ArrayList<>();
    generate(s, 0, new StringBuilder(), result);
    return result;
}

static void generate(String s, int index, StringBuilder current, List<String> result) {
    if (index == s.length()) {                            // base case: a decision was made for every character
        result.add(current.toString());
        return;
    }
    current.append(s.charAt(index));                      // choice 1: take s[index]
    generate(s, index + 1, current, result);
    current.deleteCharAt(current.length() - 1);           // undo, so the next branch starts from the same prefix
    generate(s, index + 1, current, result);              // choice 2: leave s[index] out
}

Dry run on "abc", as the recursion tree (left child = take, right child = not take):

""                       index 0
├── "a"                  take a
│   ├── "ab"             take b
│   │   ├── "abc" ✓      take c
│   │   └── "ab"  ✓      not take c
│   └── "a"              not take b
│       ├── "ac"  ✓
│       └── "a"   ✓
└── ""                   not take a
    ├── "b"
    │   ├── "bc"  ✓
    │   └── "b"   ✓
    └── ""
        ├── "c"   ✓
        └── ""    ✓

Leaves left to right: abc, ab, ac, a, bc, b, c, "". Swapping the two recursive calls would list the empty string first and s last.

Complexity. Time O(2^n · n): 2^n leaves, and copying a string of up to n characters at each. Space O(n) for the recursion depth and the shared builder.

The deleteCharAt line is the backtracking step: the builder is shared across all frames, so after exploring the take branch the character must be removed before the not-take branch runs. Forgetting it produces subsequences with extra characters.

Approach 3: Iterative doubling

Intuition. The power set of a longer string can be built from the power set of a shorter one. If P is the set of subsequences of the first i characters, then the subsequences of the first i + 1 characters are P together with every member of P extended by s[i]. Start with {""} and apply this n times; the list doubles each round, which is where 2^n comes from.

Algorithm.

  1. result = [""].
  2. For each character c of s: let size be the current size of result; for j = 0 .. size - 1, add result[j] + c.
  3. Return result.
static List<String> cascading(String s) {
    List<String> result = new ArrayList<>();
    result.add("");                                       // the power set of the empty prefix
    for (int i = 0; i < s.length(); i++) {
        int size = result.size();                         // extend only the subsequences that existed before this character
        for (int j = 0; j < size; j++) result.add(result.get(j) + s.charAt(i));
    }
    return result;
}

Complexity. Time O(2^n · n), space O(1) besides the output.

Taking size before the inner loop matters: the list grows while we iterate, and reading result.size() in the loop condition would never terminate. Interestingly this produces exactly the bit-mask order of Approach 1: adding s[i] to the first 2^i entries is the same as setting bit i.

The GeeksforGeeks output

GFG wants the non-empty subsequences sorted lexicographically. Generate with any of the three methods, drop the single empty string, and sort.

static List<String> sortedNonEmpty(String s) {
    List<String> all = recursive(s);
    all.remove("");                                       // exactly one empty subsequence exists
    Collections.sort(all);
    return all;
}

For "abc" this yields a, ab, abc, ac, b, bc, c. Sorting costs O(2^n · n · log 2^n) = O(2^n · n^2) in the worst case, so it is the dominant step, but with n ≤ 16 it is negligible.

Edge cases and pitfalls