Generate Subsequences in Java
Problem
Every subsequence of a string comes from a series of independent yes/no decisions — for each character, either keep it in the running subsequence or skip it — and recursion is a natural way to explore both choices at every position.
Given a string, generate every subsequence that can be formed by including or excluding each of its characters.
Java Program
import java.util.ArrayList;
import java.util.List;
public class GenerateSubsequencesRecursion {
static void generate(String s, int index, String current, List<String> result) {
if (index == s.length()) {
result.add(current);
return;
}
generate(s, index + 1, current, result); // exclude this character
generate(s, index + 1, current + s.charAt(index), result); // include this character
}
public static void main(String[] args) {
String s = "xy";
List<String> result = new ArrayList<>();
generate(s, 0, "", result);
System.out.println(result);
}
}Output
Core Logic
At each character position, making two recursive calls — one that leaves the character out, one that adds it in — explores every possible yes/no combination without tracking anything by hand.
- 1
generate(s, index, current, result)tracks how far through the string it's gotten and what's been decided so far. - 2The base case
if (index == s.length())fires once every character has a decision, adding whatevercurrenthas become — even if that's the empty string — to the results. - 3The first recursive call,
generate(s, index + 1, current, result), moves on without adding the current character. - 4The second,
generate(s, index + 1, current + s.charAt(index), result), appends the character before moving on.
"xy", excluding both characters reaches the base case first and adds the empty string, then excluding x but including y adds "y"; backtracking to include x produces "x" and then "xy".Key Point: Every one of the 2ⁿ leaves in this decision tree corresponds to exactly one subsequence, including the empty one — the tree's shape mirrors the yes/no choices directly, with no bitwise arithmetic needed to see why.
Why: The recursion tree has one leaf per subsequence — 2ⁿ of them for a string of length n — but the deepest chain of pending calls only ever reaches n frames before a leaf is hit and the stack unwinds.