Find All Subsequences of a String in Java
Problem
A subsequence is any selection of characters from a string that keeps their original relative order, but doesn't have to be contiguous — unlike a substring, characters can be skipped over.
Given a string, generate every one of its non-empty subsequences.
Java Program
public class FindAllSubsequences {
public static void main(String[] args) {
String str = "abc";
int n = str.length();
StringBuilder result = new StringBuilder();
// Each bitmask from 1 to 2^n - 1 represents one non-empty subset of positions to include
for (int mask = 1; mask < (1 << n); mask++) {
StringBuilder subsequence = new StringBuilder();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
subsequence.append(str.charAt(i));
}
}
if (result.length() > 0) result.append(", ");
result.append(subsequence);
}
System.out.println(result.toString());
}
}Output
Core Logic
Every non-empty subsequence corresponds to one non-zero bitmask from 1 to 2ⁿ - 1, where each set bit says 'include the character at this position.'
- 1The loop tries every
maskfrom1to(1 << n) - 1, covering every non-empty subset of thencharacter positions. - 2For each
mask, an inner loop checks every bit positionifrom0ton - 1. - 3
(mask & (1 << i)) != 0tests whether bitiis set in the current mask. - 4If it is, the character at position
iis appended to that mask's subsequence.
"abc" (n = 3), mask 1 (binary 001) selects just position 0, giving "a"; mask 5 (binary 101) selects positions 0 and 2, giving "ac".Key Point: There are 2ⁿ - 1 non-empty masks to try, and each one costs O(n) to build — so both the total work and the combined size of every subsequence printed grow as O(n × 2ⁿ), far faster than any of the O(n) or O(n²) programs elsewhere on this site.
Why: There are 2ⁿ - 1 non-empty subsets to generate, and building each one costs up to n character checks, so the total work and the size of the combined output both scale with n × 2ⁿ.
Key Concepts
Approach 2: Recursive (Include/Exclude)
import java.util.ArrayList;
import java.util.List;
public class FindAllSubsequencesRecursive {
static void generate(String str, int index, String current, List<String> result) {
if (index == str.length()) {
if (!current.isEmpty()) result.add(current);
return;
}
generate(str, index + 1, current, result); // exclude this character
generate(str, index + 1, current + str.charAt(index), result); // include it
}
public static void main(String[] args) {
String str = "abc";
List<String> result = new ArrayList<>();
generate(str, 0, "", result);
System.out.println(String.join(", ", result));
}
}
Output
Core Logic
At each character, branching into two recursive calls — one that skips it, one that includes it — explores every combination without needing to think in binary at all.
- 1The base case
if (index == str.length())fires once every character has been decided on; ifcurrentisn't empty, it's added to the results. - 2Every other call branches in two:
generate(str, index + 1, current, result)excludes the character atindex. - 3The second branch,
generate(str, index + 1, current + str.charAt(index), result), includes it instead. - 4Because both branches run for every call, all 2ⁿ combinations of include/exclude decisions get explored.
"abc", excluding every character first explores down to "c", then "b" and "bc", before backtracking to try including 'a' and exploring the rest — producing results in a different order than the bitmask version, though the same seven subsequences.Key Point: The order differs from the bitmask version because this explores 'exclude' branches before 'include' branches at every level — both are correct, just different traversal orders over the same set of combinations.
Why: Each of the 2ⁿ recursive branches builds its own subsequence string via concatenation, and together they still produce the same total O(n × 2ⁿ) characters as the bitmask version — this time via string concatenation instead of a StringBuilder.