Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Understanding Subsequences

MEDIUMProblemSolveExternal Links

Description

A subsequence of a string (or array) is a new sequence formed by selecting zero or more characters from the original, without changing their relative order. Unlike a substring, the selected characters do not need to be consecutive.

For example, given the string "abc":

  • "ac" is a subsequence (we picked 'a' and 'c', skipping 'b', but their left-to-right order is preserved)
  • "ca" is not a subsequence (the order of 'c' and 'a' is reversed)
  • "abc" is a subsequence (the full string itself)
  • "" (empty string) is a subsequence (we pick nothing)

Given a string s, generate all possible subsequences of s.

Key properties of subsequences:

  • A string of length n has exactly 2^n subsequences (including the empty string), because each character is independently either included or excluded.
  • Every substring is a subsequence, but not every subsequence is a substring.
  • The relative order of characters in a subsequence always matches their order in the original string.

Examples

Example 1

Input: s = "ab"

Output: ["", "a", "ab", "b"]

Explanation: With 2 characters, there are 2² = 4 subsequences. For each character, we independently decide to include or exclude it:

  • Exclude both → ""
  • Include 'a' only → "a"
  • Include 'b' only → "b"
  • Include both → "ab"

Example 2

Input: s = "abc"

Output: ["", "a", "ab", "abc", "ac", "b", "bc", "c"]

Explanation: With 3 characters, there are 2³ = 8 subsequences. Each combination of include/exclude decisions across the three positions produces a unique subsequence. For instance, including 'a' and 'c' but excluding 'b' gives "ac" — note that 'a' still appears before 'c', preserving the original order.

Example 3

Input: s = "a"

Output: ["", "a"]

Explanation: A single-character string has exactly 2 subsequences: the empty string and the character itself.

Constraints

  • 1 ≤ s.length ≤ 20
  • s consists of lowercase English letters only

Editorial

Brute Force - Bit Masking

Intuition

Since each character in the string is either included or excluded from a subsequence, we can think of every subsequence as a binary decision for each position: 1 means "include this character" and 0 means "skip it".

For a string of length n, there are 2^n possible combinations of these binary decisions — which is exactly the set of integers from 0 to 2^n − 1. Each integer's binary representation serves as a "mask" that tells us which characters to pick.

Imagine you have a row of light switches, one for each character. Flipping different combinations of switches on and off gives you every possible subsequence. The number of switch combinations equals 2^n.

For s = "ab":

  • Mask 0 (binary 00): no switches on → "" (empty)
  • Mask 1 (binary 01): switch for 'a' on → "a"
  • Mask 2 (binary 10): switch for 'b' on → "b"
  • Mask 3 (binary 11): both switches on → "ab"

Step-by-Step Explanation

Let's trace through with s = "ab" (n = 2):

Step 1: Compute total masks = 2^n = 4. We iterate mask from 0 to 3.

Step 2: mask = 0 (binary: 00).

  • Check bit 0: (0 & 1) = 0 → skip 'a'
  • Check bit 1: (0 & 2) = 0 → skip 'b'
  • Subsequence = "" (empty string). Add to result.
  • Result: [""]

Step 3: mask = 1 (binary: 01).

  • Check bit 0: (1 & 1) = 1 → include 'a'
  • Check bit 1: (1 & 2) = 0 → skip 'b'
  • Subsequence = "a". Add to result.
  • Result: ["", "a"]

Step 4: mask = 2 (binary: 10).

  • Check bit 0: (2 & 1) = 0 → skip 'a'
  • Check bit 1: (2 & 2) = 2 (nonzero) → include 'b'
  • Subsequence = "b". Add to result.
  • Result: ["", "a", "b"]

Step 5: mask = 3 (binary: 11).

  • Check bit 0: (3 & 1) = 1 → include 'a'
  • Check bit 1: (3 & 2) = 2 (nonzero) → include 'b'
  • Subsequence = "ab". Add to result.
  • Result: ["", "a", "b", "ab"]

Step 6: mask = 4 equals total (4). Stop. Final result: ["", "a", "b", "ab"].

Bit Masking — Enumerating All Subsequences of "ab" — Watch how each bitmask from 0 to 2^n − 1 selects a unique combination of characters, producing every possible subsequence.

Algorithm

  1. Compute total = 2^n where n is the length of the string
  2. For each mask from 0 to total − 1:
    a. Initialize an empty subsequence string
    b. For each position j from 0 to n − 1:
    • If the j-th bit of mask is set (mask & (1 << j) is nonzero), append s[j] to the subsequence
      c. Add the subsequence to the result list
  3. Return the result list

Code

#include <vector>
#include <string>
#include <cmath>
using namespace std;

class Solution {
public:
    vector<string> generateSubsequences(string s) {
        vector<string> result;
        int n = s.size();
        int total = 1 << n; // 2^n
        
        for (int mask = 0; mask < total; mask++) {
            string subseq;
            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) {
                    subseq += s[j];
                }
            }
            result.push_back(subseq);
        }
        
        return result;
    }
};
class Solution:
    def generateSubsequences(self, s: str) -> list[str]:
        result = []
        n = len(s)
        total = 1 << n  # 2^n
        
        for mask in range(total):
            subseq = ""
            for j in range(n):
                if mask & (1 << j):
                    subseq += s[j]
            result.append(subseq)
        
        return result
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> generateSubsequences(String s) {
        List<String> result = new ArrayList<>();
        int n = s.length();
        int total = 1 << n; // 2^n
        
        for (int mask = 0; mask < total; mask++) {
            StringBuilder subseq = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) {
                    subseq.append(s.charAt(j));
                }
            }
            result.add(subseq.toString());
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × 2^n)

We iterate through 2^n masks. For each mask, we check all n bit positions to determine which characters to include. Additionally, building each subsequence string takes up to O(n) time. Total: 2^n masks × O(n) work per mask = O(n × 2^n).

Space Complexity: O(n)

Excluding the output, we use O(n) space for the temporary subsequence string being built. The output itself stores all 2^n subsequences, requiring O(n × 2^n) space total, but this is inherent to the problem's output.

Why This Approach Is Not Efficient

The bit masking approach achieves O(n × 2^n) time, which matches the theoretical lower bound — we must generate all 2^n subsequences, each of length up to n. However, the approach has significant practical and conceptual limitations:

1. Wasted computation on every mask: For each of the 2^n masks, we scan all n bits even though most masks only select a few characters. The inner loop always runs n times regardless of how many bits are set.

2. No early termination or pruning: If the problem required only subsequences satisfying a condition (e.g., subsequences that sum to a target, or subsequences of a certain length), the bit masking approach would still generate all 2^n candidates before filtering. There is no way to skip entire branches of the search space.

3. Integer overflow limitation: The approach represents the mask as an integer. For n > 30 (32-bit integer) or n > 62 (64-bit integer), this method fails entirely. While n ≤ 20 in our constraints, the recursive approach has no such coupling to integer size.

4. Non-intuitive for learning: Bit manipulation obscures the fundamental recursive structure of subsequence generation — the elegant "pick or don't pick" decision tree.

Key insight for improvement: Generating subsequences has a natural recursive structure. At each character position, you make a binary choice: include it or skip it. This directly maps to a recursion tree where the left branch includes the character and the right branch excludes it. This recursive formulation is more intuitive, more flexible (supports pruning), and is the standard pattern used across many subsequence-related problems.

Optimal Approach - Recursion (Pick or Don't Pick)

Intuition

Imagine you're walking through a buffet line with dishes labeled 'a', 'b', 'c' in order. At each dish, you have exactly two choices: put it on your plate (include it) or walk past it (exclude it). You must visit the dishes in order — you cannot go back. Every unique combination of picks and skips gives you a different plate of food — a different subsequence.

This is the "pick or don't pick" pattern, one of the most fundamental recursive strategies in computer science:

  1. Base case: When you've walked past all dishes (processed all characters), whatever is on your plate is one complete subsequence. Record it.
  2. Recursive step: At character position i:
    • Pick: Add s[i] to the current subsequence, then move to position i+1
    • Don't pick: Leave the current subsequence unchanged, then move to position i+1

Since we always try "pick" before "don't pick" (or vice versa) and process characters left to right, the recursion naturally explores all 2^n combinations. The recursion tree has depth n (one level per character) and 2^n leaves (one per subsequence).

This approach is superior to bit masking not because of asymptotic complexity (both are O(n × 2^n)), but because the recursive structure directly models the problem's logic and generalizes effortlessly to constrained subsequence problems through pruning.

Step-by-Step Explanation

Let's trace with s = "ab" (n = 2). We start with an empty current subsequence at position 0.

Step 1: Call generate(pos=0, current=""). We're at character 'a'. Two choices: include 'a' or skip 'a'. Try including first.

Step 2: INCLUDE 'a'. Current becomes "a". Call generate(pos=1, current="a"). Now at character 'b'.

Step 3: INCLUDE 'b'. Current becomes "ab". Call generate(pos=2, current="ab"). Position 2 equals n — base case reached. "ab" is a complete subsequence. Add to result. Result: ["ab"].

Step 4: Backtrack to pos=1 with current="a". Now try the other choice: EXCLUDE 'b'. Current stays "a". Call generate(pos=2, current="a"). Base case. "a" is a complete subsequence. Add to result. Result: ["ab", "a"].

Step 5: Backtrack to pos=0 with current="". We've explored all paths with 'a' included. Now EXCLUDE 'a'. Current stays "". Call generate(pos=1, current=""). Now at character 'b'.

Step 6: INCLUDE 'b'. Current becomes "b". Call generate(pos=2, current="b"). Base case. "b" is a complete subsequence. Add to result. Result: ["ab", "a", "b"].

Step 7: Backtrack to pos=1 with current="". EXCLUDE 'b'. Current stays "". Call generate(pos=2, current=""). Base case. "" (empty) is a complete subsequence. Add to result. Result: ["ab", "a", "b", ""].

Step 8: All recursive paths exhausted. Final result: ["ab", "a", "b", ""] — all 4 subsequences found.

Pick or Don't Pick — Generating All Subsequences of "ab" — Watch the recursion tree unfold as each character faces a binary choice: include it in the subsequence or skip it. Every leaf is a complete subsequence.

Algorithm

  1. Create an empty result list
  2. Define a recursive function generate(pos, current):
    a. Base case: If pos equals n (string length), add a copy of current to the result list and return
    b. Pick: Append s[pos] to current, call generate(pos + 1, current), then remove s[pos] (backtrack)
    c. Don't pick: Call generate(pos + 1, current) without modifying current
  3. Call generate(0, "") to start from position 0 with an empty subsequence
  4. Return the result list

Code

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    void generate(const string& s, int pos, string& current,
                  vector<string>& result) {
        if (pos == s.size()) {
            result.push_back(current);
            return;
        }
        
        // Pick: include s[pos] in the subsequence
        current.push_back(s[pos]);
        generate(s, pos + 1, current, result);
        current.pop_back(); // backtrack
        
        // Don't pick: skip s[pos]
        generate(s, pos + 1, current, result);
    }
    
    vector<string> generateSubsequences(string s) {
        vector<string> result;
        string current;
        generate(s, 0, current, result);
        return result;
    }
};
class Solution:
    def generateSubsequences(self, s: str) -> list[str]:
        result = []
        
        def generate(pos: int, current: list[str]):
            if pos == len(s):
                result.append("".join(current))
                return
            
            # Pick: include s[pos]
            current.append(s[pos])
            generate(pos + 1, current)
            current.pop()  # backtrack
            
            # Don't pick: skip s[pos]
            generate(pos + 1, current)
        
        generate(0, [])
        return result
import java.util.ArrayList;
import java.util.List;

class Solution {
    private void generate(String s, int pos, StringBuilder current,
                          List<String> result) {
        if (pos == s.length()) {
            result.add(current.toString());
            return;
        }
        
        // Pick: include s[pos]
        current.append(s.charAt(pos));
        generate(s, pos + 1, current, result);
        current.deleteCharAt(current.length() - 1); // backtrack
        
        // Don't pick: skip s[pos]
        generate(s, pos + 1, current, result);
    }
    
    public List<String> generateSubsequences(String s) {
        List<String> result = new ArrayList<>();
        generate(s, 0, new StringBuilder(), result);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × 2^n)

The recursion tree has 2^n leaf nodes, one for each subsequence. At each leaf, we copy the current subsequence (up to length n) into the result, costing O(n). The internal nodes perform O(1) work each (appending/removing a character and making recursive calls). With 2^n − 1 internal nodes, total time is O(n × 2^n) for leaf copies plus O(2^n) for internal processing, giving O(n × 2^n) overall.

Space Complexity: O(n)

The recursion stack depth is n (one level per character in the string). We maintain a single mutable current string of length at most n. Excluding the output storage, auxiliary space is O(n). The output requires O(n × 2^n) space to store all subsequences, but that is inherent to the problem.

Why this is the preferred approach:
While both approaches share the same asymptotic complexity, the recursive "pick or don't pick" pattern:

  • Directly models the problem's combinatorial structure
  • Supports pruning for constrained variants (e.g., subsequences with sum = k)
  • Is the foundational pattern for subset generation, combination generation, and backtracking problems
  • Uses no bit manipulation, making it accessible to beginners