Introduction

A subsequence is any sequence you get by keeping characters in their original order and optionally skipping some of them. For a string of length n, there are 2^n subsequences, so the main challenge is not the algorithm itself but understanding the growth rate and generating them cleanly.

The Core Idea

For each character, you have exactly two choices:

• include it in the current subsequence
• exclude it from the current subsequence

That binary choice naturally leads to recursion or to a bitmask-based loop. Both approaches generate the same result set.

For the string "abc", the subsequences are:

• '""'
• '"a"'
• '"b"'
• '"c"'
• '"ab"'
• '"ac"'
• '"bc"'
• '"abc"'

The empty string is a valid subsequence unless your problem statement explicitly says to omit it.

Java Recursive Solution

A recursive backtracking solution is usually the clearest way to express the problem.

1import java.util.ArrayList;
2import java.util.List;
3
4public class Subsequences {
5    public static List<String> allSubsequences(String s) {
6        List<String> result = new ArrayList<>();
7        build(s, 0, new StringBuilder(), result);
8        return result;
9    }
10
11    private static void build(String s, int index, StringBuilder current, List<String> result) {
12        if (index == s.length()) {
13            result.add(current.toString());
14            return;
15        }
16
17        build(s, index + 1, current, result);
18
19        current.append(s.charAt(index));
20        build(s, index + 1, current, result);
21        current.deleteCharAt(current.length() - 1);
22    }
23
24    public static void main(String[] args) {
25        List<String> subsequences = allSubsequences("abc");
26        for (String value : subsequences) {
27            System.out.println('[' + value + ']');
28        }
29    }
30}

This works by exploring the “skip” branch first and the “take” branch second. The exact output order can vary depending on the branch order, but the set of subsequences is the same.

Bitmask Alternative

If you prefer an iterative solution, use the binary representation of numbers from 0 to 2^n - 1. Each bit says whether the character at that position should be included.

1public static void printSubsequencesBitmask(String s) {
2    int n = s.length();
3    int total = 1 << n;
4
5    for (int mask = 0; mask < total; mask++) {
6        StringBuilder current = new StringBuilder();
7        for (int i = 0; i < n; i++) {
8            if ((mask & (1 << i)) != 0) {
9                current.append(s.charAt(i));
10            }
11        }
12        System.out.println('[' + current.toString() + ']');
13    }
14}

This version is compact and easy to reason about if you are comfortable with bit operations.

C++ Version

The same recursive idea translates directly to C++.

1#include <iostream>
2#include <string>
3#include <vector>
4
5void build(const std::string& s, int index, std::string& current, std::vector<std::string>& out) {
6    if (index == static_cast<int>(s.size())) {
7        out.push_back(current);
8        return;
9    }
10
11    build(s, index + 1, current, out);
12
13    current.push_back(s[index]);
14    build(s, index + 1, current, out);
15    current.pop_back();
16}
17
18int main() {
19    std::vector<std::string> out;
20    std::string current;
21    build("abc", 0, current, out);
22
23    for (const auto& value : out) {
24        std::cout << '[' << value << "]\n";
25    }
26}

If you need the result in sorted order, sort the output afterward. Subsequence generation itself does not imply lexicographic order.

Repeated Characters Change The Situation

If the input contains duplicate letters, such as "aab", the naive algorithm still explores 2^n positions, but some generated subsequences will be identical. Whether that is correct depends on the problem.

• If the task is to enumerate subsequences by index choice, duplicates are expected.
• If the task is to list unique subsequence strings, store results in a Set or deduplicate after generation.

Do not silently change this behavior unless you know which interpretation the problem expects.

Complexity Matters

Time complexity is O(n * 2^n) if you account for constructing output strings. Space usage also grows quickly if you store every result.

That means generating all subsequences is practical only for small strings. At length 20, you already have over one million subsequences. Sometimes the correct solution is not to materialize them all, but to process each subsequence on the fly.

Common Pitfalls

The biggest pitfall is confusing subsequences with substrings. Substrings must stay contiguous. Subsequences only preserve relative order.

Another common mistake is forgetting the empty subsequence. Many textbook definitions include it, so verify the requirement before dropping it.

People also underestimate duplicate handling when the string contains repeated characters. A correct index-based generator can still produce repeated strings.

Finally, do not ignore the exponential growth. The algorithm is simple, but the output size dominates quickly.

Summary

• Every character creates two choices: include or exclude.
• Recursive backtracking is the clearest general solution.
• A bitmask loop is a clean iterative alternative.
• Duplicate input characters can create duplicate subsequence strings.
• Generating all subsequences is inherently exponential, so use it only for small inputs.