☕ DSA Java Articles

Topics › Recursion and Backtracking › Subsequences Pattern

Power Set (this is very important)

Medium TUF ID 2856 SDE

Java source ↗ Edit this article ↗

Problem

Given a string s of length n, return every non-empty subsequence of s in lexicographically sorted order. A subsequence keeps some of the characters (at least one) in their original relative order; it does not need to be contiguous. This list is the power set of the characters of s, minus the empty set.

Typical constraints (GeeksforGeeks “Power Set”): 1 ≤ n ≤ 16, lowercase letters. The output has 2^n - 1 strings, so n has to be small.

The Striver SDE sheet lists it on the Trie day, next to the maximum-XOR problems, which also require thinking about numbers bit by bit; the bitmask enumeration below is a gentle introduction to that habit. The same three techniques also solve LeetCode 78 “Subsets”, which asks for the power set of an integer array.

Example 1

s = "abc"
answer = [a, ab, abc, ac, b, bc, c]       // 2^3 - 1 = 7 subsequences, sorted

Example 2

s = "ba"
answer = [a, b, ba]          // "ab" is not a subsequence: order inside each one follows s

A subsequence is identified by which positions it uses. If s has repeated letters, two different position sets can spell the same string: "aa" yields [a, a, aa]. This article keeps those repeats, which is what the GeeksforGeeks version expects; use a TreeSet instead of a list if your version wants distinct strings.

Why there are 2^n of them

Each of the n characters independently is either in the subsequence or not. Two choices, n times, gives 2^n combinations, one of which is “take nothing”. All three approaches below enumerate exactly those 2^n yes/no patterns; they differ only in how they walk through them. Since writing out each subsequence costs up to n characters, O(n × 2^n) is the best possible time for producing the output, so every approach here is optimal in that sense. Sorting adds a factor on top, discussed under complexity.

Approach 1: Recursion (pick / not pick)

Intuition. Walk through s one index at a time. At index i, branch twice: once with s[i] appended to the current subsequence, once without. When i reaches n, every character has been decided, so the current builder is one complete subsequence. The recursion tree is a full binary tree of depth n, and its 2^n leaves are exactly the subsets.

Using a single StringBuilder and undoing the append after the “pick” branch (backtracking) avoids creating a new string at every level.

Algorithm.

  1. generate(i, cur): if i == n, record cur if it is non-empty and return.
  2. Append s[i], call generate(i + 1), remove the last character.
  3. Call generate(i + 1) without s[i].
  4. Sort the collected list.
static List<String> recursion(String s) {
    List<String> out = new ArrayList<>();
    generate(0, s, new StringBuilder(), out);
    Collections.sort(out);
    return out;
}

static void generate(int i, String s, StringBuilder cur, List<String> out) {
    if (i == s.length()) {
        if (cur.length() > 0) out.add(cur.toString());     // every leaf is one subsequence; skip the empty one
        return;
    }
    cur.append(s.charAt(i));                               // pick s[i]
    generate(i + 1, s, cur, out);
    cur.deleteCharAt(cur.length() - 1);                    // undo the pick
    generate(i + 1, s, cur, out);                          // do not pick s[i]
}

Complexity. Time O(n × 2^n) to generate, plus the sort (below). Space O(n) for the recursion stack and builder, beyond the output itself.

Approach 2: Bitmask enumeration

Intuition. Write the yes/no pattern as an n-bit binary number: bit i is 1 when s[i] is included. Then the 2^n patterns are simply the integers 0 to 2^n - 1. Counting from 1 (skipping 0, the empty set) to 2^n - 1 visits every non-empty subsequence exactly once, with no recursion at all. Testing bit i is (mask & (1 << i)) != 0.

Algorithm.

  1. For mask from 1 to (1 << n) - 1:
  2. Build a string from every s[i] with bit i of mask set, in increasing i.
  3. Add it to the list; sort at the end.
static List<String> bitmask(String s) {
    int n = s.length();
    List<String> out = new ArrayList<>();
    for (int mask = 1; 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));
        }
        out.add(sb.toString());
    }
    Collections.sort(out);
    return out;
}

Dry run on s = "abc" (bit 0 is the rightmost and stands for a):

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

Sorting gives [a, ab, abc, ac, b, bc, c].

Complexity. Time O(n × 2^n) to generate (each of the 2^n - 1 masks inspects n bits), plus the sort. Space O(n) beyond the output. An int mask works for n ≤ 30; the output would be far too large long before that.

Approach 3: Iterative doubling

Intuition. Suppose we already have every subsequence of the first i characters. The subsequences of the first i + 1 characters are those same ones, plus each of them with s[i] appended. So start with [""] and, for each character, append it to every existing entry, doubling the list. Record the size before the inner loop; otherwise we would keep extending entries we just added.

Algorithm.

  1. all = [""].
  2. For each character c: let size = all.size(); for k < size, add all[k] + c.
  3. Remove the empty string (index 0), sort, return.
static List<String> iterative(String s) {
    List<String> all = new ArrayList<>();
    all.add("");
    for (char c : s.toCharArray()) {
        int size = all.size();                             // only extend what existed before this character
        for (int k = 0; k < size; k++) all.add(all.get(k) + c);
    }
    all.remove(0);                                         // drop the empty subsequence
    Collections.sort(all);
    return all;
}

Complexity. Time O(n × 2^n) to generate, plus the sort. Space: the list itself is the output.

Sorting and its cost

All three methods produce subsequences in an order that is convenient for the method, not alphabetical, so each ends with Collections.sort. Sorting 2^n strings takes O(2^n × log(2^n)) = O(n × 2^n) comparisons, each up to O(n) characters, so O(n^2 × 2^n) in the worst case. For n = 16 that is a few million character comparisons, well within limits.

If s is already sorted and has no repeated letters, a depth-first search that extends the current string with each later character in turn (a, ab, abc, ac, b, bc, c) emits the answer already in order. With repeated letters that ordering breaks (for "aab" it would place the second "a" after "ab"), which is why the code here simply sorts.

Edge cases and pitfalls