Print all Subsequences of a string
Problem Statement
Given a string, print all possible subsequences of the string. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example:
-
Input:
"abc" -
Output:
["", "a", "b", "c", "ab", "ac", "bc", "abc"] -
Input:
"ab" -
Output:
["", "a", "b", "ab"]
Note: A string of length n has 2^n subsequences (including the empty string).
Approach 1: Recursion (Pick/Not Pick)
Intuition
For each character, we have two choices: include it in the current subsequence or exclude it. This creates a binary decision tree.
Algorithm
- For each character at index i:
- Include it and recurse for remaining string
- Exclude it and recurse for remaining string
- When we reach the end, add the current subsequence to result
import java.util.*;
public class Solution {
public List<String> getAllSubsequences(String s) {
List<String> result = new ArrayList<>();
generateSubsequences(s, 0, "", result);
return result;
}
private void generateSubsequences(String s, int index, String current,
List<String> result) {
// Base case: reached end of string
if (index == s.length()) {
result.add(current);
return;
}
// Exclude current character
generateSubsequences(s, index + 1, current, result);
// Include current character
generateSubsequences(s, index + 1, current + s.charAt(index), result);
}
// Using StringBuilder for efficiency
public List<String> getAllSubsequencesEfficient(String s) {
List<String> result = new ArrayList<>();
generateSubsequencesEfficient(s, 0, new StringBuilder(), result);
return result;
}
private void generateSubsequencesEfficient(String s, int index,
StringBuilder current,
List<String> result) {
if (index == s.length()) {
result.add(current.toString());
return;
}
// Exclude
generateSubsequencesEfficient(s, index + 1, current, result);
// Include
current.append(s.charAt(index));
generateSubsequencesEfficient(s, index + 1, current, result);
current.deleteCharAt(current.length() - 1);
}
}Complexity Analysis
- Time Complexity: O(2^n × n) - 2^n subsequences, each taking O(n) to construct
- Space Complexity: O(n) - Recursion stack depth
Approach 2: Iterative (Bit Manipulation)
Intuition
Each subsequence can be represented by a binary number where bit i indicates whether character i is included. For n characters, there are 2^n possible binary numbers (0 to 2^n - 1).
Algorithm
- Iterate from 0 to 2^n - 1
- For each number, check which bits are set
- Include characters at positions where bits are set
import java.util.*;
public class Solution {
public List<String> getAllSubsequences(String s) {
int n = s.length();
int total = 1 << n; // 2^n
List<String> result = new ArrayList<>();
for (int mask = 0; mask < total; mask++) {
StringBuilder subsequence = new StringBuilder();
for (int i = 0; i < n; i++) {
// Check if ith bit is set
if ((mask & (1 << i)) != 0) {
subsequence.append(s.charAt(i));
}
}
result.add(subsequence.toString());
}
return result;
}
}Complexity Analysis
- Time Complexity: O(2^n × n) - 2^n iterations, each checking n bits
- Space Complexity: O(1) - Not counting output storage
Approach 3: Using Power Set Library (Python)
Intuition
Python's itertools provides a combinations function that can generate all subsequences.
Approach 4: Excluding Empty Subsequence (Non-empty only)
Intuition
Sometimes we need only non-empty subsequences. We can modify our approaches to exclude the empty string.
public class Solution {
public List<String> getNonEmptySubsequences(String s) {
int n = s.length();
int total = 1 << n;
List<String> result = new ArrayList<>();
for (int mask = 1; mask < total; mask++) { // Start from 1
StringBuilder subsequence = new StringBuilder();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
subsequence.append(s.charAt(i));
}
}
result.add(subsequence.toString());
}
return result;
}
}Handling Duplicates
If the string contains duplicate characters and we want unique subsequences:
Key Takeaways
- 2^n subsequences exist for a string of length n (including empty)
- Recursion (Pick/Not Pick) is the most intuitive approach
- Bit manipulation provides an elegant iterative solution
- Each subsequence maps to a binary number from 0 to 2^n - 1
- Time complexity is exponential - unavoidable since output is exponential
- Use StringBuilder/list for efficient string construction
- For unique subsequences with duplicates, use a Set
- This technique is fundamental for many backtracking problems