Print all Subsequences of a string

The problem, simply

A subsequence of a string is what you get when you cross out some letters (maybe none, maybe all) and keep the rest in the same order. From abc you can get ac by crossing out b, but never ca, because that changes the order.

Print every subsequence of the string. The empty string counts. A string with n letters has 2^n of them, because each letter is either kept or crossed out.

A story to remember it

Picture it

Examples

Way 1: the simple way

Count from 0 to 2^n - 1 in binary. Each number is a row of yes and no switches, one for each letter: bit i set means "keep letter i". Every number gives a different set of switches, so every subsequence shows up exactly once.

1. For mask from 0 to 2^n - 1.
2. For each i, if bit i of mask is 1, add s[i].
3. Print what you built.

import java.util.*;

class Solution {
    public List<String> allSubsequences(String s) {
        int n = s.length();
        List<String> out = 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));   // switch i is on
            }
            out.add(sb.toString());
        }
        return out;
    }
}

How long it takes: 2^n masks, and each one looks at n bits, so O(n * 2^n). Extra room: one builder of up to n letters, O(n), not counting the answers. It only works while n fits in the bits of an int, about 30 letters, which is already a billion answers.

Way 2: the clever way

Walk the choice tree with recursion. At letter i, first take it and solve the rest, then skip it and solve the rest. When i reaches the end, the bag is one answer. Use one shared builder: add the letter before going down, and remove it when you come back up. That undo step is called backtracking.

This way is easier to change. You can stop early (prune) on a branch that cannot work, skip repeated letters, or only keep answers of a certain length.

import java.util.*;

class Solution {
    public List<String> allSubsequences(String s) {
        List<String> out = new ArrayList<>();
        walk(s, 0, new StringBuilder(), out);
        return out;
    }

    private void walk(String s, int i, StringBuilder bag, List<String> out) {
        if (i == s.length()) {             // every letter decided
            out.add(bag.toString());
            return;
        }
        bag.append(s.charAt(i));           // take letter i
        walk(s, i + 1, bag, out);
        bag.deleteCharAt(bag.length() - 1);   // undo the take
        walk(s, i + 1, bag, out);          // skip letter i
    }
}

How long it takes: the tree has 2^n bottom ends, and copying each answer costs up to n, so O(n * 2^n). No method can beat that, because the answers alone have that many letters. Extra room: the recursion goes n levels deep and shares one builder, O(n), not counting the answers.

Watch out for

• The empty subsequence is an answer. Some problems want only non-empty ones, then start the mask at 1 or skip the empty bag.
• s + c in each call makes a new string every time. It works, but it is slower than one shared builder.
• A substring keeps letters next to each other. A subsequence may jump. ac is a subsequence of abc but not a substring.
• For 20 letters there are over a million answers. Ask if you must print them, or only count them (2^n).

What interviewers ask next

• Only different subsequences, when letters repeat? Use a set, or sort the letters and, at each position, skip a letter equal to the one tried just before it at the same level.
• Count the different subsequences without listing them? Use dynamic programming over the first i letters, with dp[0] = 1 for the empty string: dp[i] = 2 * dp[i - 1], minus dp[j - 1] if the same letter last appeared at position j (counting from 1). For aab that gives 2, 3, 6.
• Print them in dictionary order? Sort the list at the end, or build them with a "for each next letter" recursion over sorted letters.
• All subsets of a set of numbers? Exactly the same tree. Subsets of an array are subsequences.
• Subsequences whose sum is k? Same tree, carry the sum, and cut a branch early when the numbers are all positive and the sum is already too big.

Remember this

Grown-up words: the snack bag choices are a binary decision tree, walking it with undo is backtracking, the yes and no switches are a bitmask, and the full list of subsets is the power set.