🚀 Supercharge your YouTube channel's growth with AI.
Try YTGrowAI FreePrint All Possible Subsequences/Subsets in Python
You have a string and you want to list every possible combination of its characters. The order matters, and each character can either show up in a combination or vanish. That is the subsequence problem. I ran into it first during a college placement drive, then again during a coding interview at a fintech startup. It keeps appearing because it tests your understanding of recursion at a fundamental level. This tutorial breaks the problem down until there is nothing left to hide.
By the end of this guide you will understand why the recursive approach works, how to implement it in Python, and what the time and space complexity look like. You will also see a complete dry run on the string “abc” so there are no gaps in your mental model before you run the code yourself.
What Is a Subsequence?
A subsequence is a sequence derived from another sequence by deleting some or no elements without changing the order of the remaining elements. The characters do not need to sit next to each other in the original string. “ace” is a subsequence of “abcde” because you can drop “b” and “d” and retain the order. “cae” is not a subsequence because the order changes.
Subsets and subsequences are closely related. For a string of length n, every subsequence is also a subset of the character positions. The difference is subtle but important: a subset treats the string as a set of unique characters while a subsequence preserves order. This tutorial focuses on subsequences of a string, which means order is always part of the constraint.
The Core Idea: Two Choices at Every Step
Recursion becomes intuitive once you strip the problem to its barest bones. At every index in the string you have exactly two choices. You can include the current character in your output string and recurse on the rest, or you can skip it and recurse anyway. That is the entire decision tree.
Consider the string “abc”. At index 0 you encounter “a”. You branch into two recursive calls: one where “a” is part of the output and one where it is not. At index 1 you encounter “b” and each of those branches splits again. By the time you reach the end of the string you have explored every combination of include/skip decisions, which gives you every possible subsequence.
The recursion terminates when you reach the length of the string. At that point you print whatever output string you have accumulated. The empty output string is a valid subsequence, representing the case where you skipped every character.
Python Implementation
Here is the complete, working Python code. Copy this into a file and run it.
def get_all_subsequence(string, output, index):
if index == len(string):
if len(output) != 0:
print(output)
return
# Exclude current character, recurse on the rest
get_all_subsequence(string, output, index + 1)
# Include current character, recurse on the rest
get_all_subsequence(string, output + string[index], index + 1)
if __name__ == "__main__":
user_input = input("Enter a string: ")
get_all_subsequence(user_input, "", 0)
The function takes three arguments. string is the source. output accumulates characters as we decide to include them. index tracks our current position. When index reaches the end of the string we have exhausted all choices and we print. Otherwise we branch twice: once without the current character and once with it appended to output.
Dry Run on “abc”
Walking through the execution by hand removes all ambiguity. Let me trace every call for the input “abc”.
Call 1: get_all_subsequence("abc", "", 0). We are at index 0 (“a”). Two branches form.
Branch 1 (exclude “a”): get_all_subsequence("abc", "", 1). We are at index 1 (“b”). Two branches form.
Branch 1a (exclude “b”): get_all_subsequence("abc", "", 2). We are at index 2 (“c”). Two branches form.
Branch 1a-i (exclude “c”): get_all_subsequence("abc", "", 3). Index equals length. Output is empty. Nothing printed. Return.
Branch 1a-ii (include “c”): get_all_subsequence("abc", "c", 3). Index equals length. Output is “c”. Print “c”. Return.
Branch 1b (include “b”): get_all_subsequence("abc", "b", 2). We are at index 2 (“c”). Two branches form.
Branch 1b-i (exclude “c”): get_all_subsequence("abc", "b", 3). Index equals length. Output is “b”. Print “b”. Return.
Branch 1b-ii (include “c”): get_all_subsequence("abc", "bc", 3). Index equals length. Output is “bc”. Print “bc”. Return.
Branch 2 (include “a”): get_all_subsequence("abc", "a", 1). We are at index 1 (“b”). Two branches form.
Branch 2a (exclude “b”): get_all_subsequence("abc", "a", 2). We are at index 2 (“c”). Two branches form.
Branch 2a-i (exclude “c”): get_all_subsequence("abc", "a", 3). Index equals length. Output is “a”. Print “a”. Return.
Branch 2a-ii (include “c”): get_all_subsequence("abc", "ac", 3). Index equals length. Output is “ac”. Print “ac”. Return.
Branch 2b (include “b”): get_all_subsequence("abc", "ab", 2). We are at index 2 (“c”). Two branches form.
Branch 2b-i (exclude “c”): get_all_subsequence("abc", "ab", 3). Index equals length. Output is “ab”. Print “ab”. Return.
Branch 2b-ii (include “c”): get_all_subsequence("abc", "abc", 3). Index equals length. Output is “abc”. Print “abc”. Return.
Output
Running the code with “abc” as input produces eight lines of output. The empty line represents the subsequence where every character was skipped. Every other line shows a non-empty subsequence.
Enter a string: abc
c
b
bc
a
ac
ab
abc
The eight outputs match the eight leaf nodes in the recursion tree we traced above. For a string of length n, the total number of subsequences is always 2 raised to the power of n. This is because each of the n positions has two choices (include or exclude) and the choices multiply together.
Time and Space Complexity
The time complexity is O(2^n) because the recursive tree has exactly 2^n leaf nodes and the work done at each node is constant. The total number of nodes in the tree is also O(2^n) when you count internal nodes, so the overall time complexity is dominated by the number of leaves.
The space complexity is O(n) for the recursion depth. At any point in the call stack you are holding at most n characters in the output string, which corresponds to the maximum depth of the recursion tree. The output string itself contributes to space complexity because Python strings are immutable and each concatenation creates a new string object.
Common Mistakes to Avoid
The most frequent bug I see in submissions is modifying output in place and then forgetting to backtrack. If you append a character to output before recursing, you must remove it after the recursive call returns. Failing to backtrack produces duplicate subsequences because the same character accumulates across multiple branches.
Another mistake is printing inside the recursive call before checking the base case. The print statement must live inside the if index == len(string) block. Placing it outside produces nothing but the last character repeated n times.
A third issue is using string concatenation incorrectly. output += string[index] creates a new string object on each call. For large n this is expensive. Using a list and converting to a string at the end is a valid optimization, though for interview purposes the simple string version is usually fine.
Variations and Extensions
The subsequence pattern extends beyond printing combinations. The same two-choice recursion solves subset sum problems, combination sum, and power set generation. If you have an array of numbers and you want all subsets that sum to a target, you apply the same include/skip logic but accumulate a running sum instead of a string.
You can also adapt the pattern to handle duplicates. If the input string has repeated characters, the naive approach produces duplicate subsequences. Sort the input first, then skip recursive branches where the current character equals the previous character and you have already explored a branch that skipped that previous character. This is the same deduplication logic used in the standard subsets-with-duplicates problem.
For subsequences of an array rather than a string, the implementation is identical except you index into the list instead of using string indexing. The branching logic does not change at all.
FAQ
Why does the recursion generate all subsequences and not just some of them?
Because the recursion explores every possible combination of include/skip decisions. For n characters there are 2^n such combinations. The decision tree is exhaustive by construction. Each leaf node in the tree corresponds to exactly one subsequence.
Can subsequences contain duplicate characters?
Yes, if the original string contains duplicate characters. For example, the string “aab” produces the subsequences “a”, “a”, “aa”, “ab”, “aab”, and the empty string. The two “a” characters are indistinguishable in the output even though they came from different positions. If you want unique subsequences you need to deduplicate the output, which adds complexity beyond the scope of this basic implementation.
What is the difference between a subsequence and a substring?
A substring must consist of contiguous characters from the original string. A subsequence does not require contiguity. “abc” is a substring of “XabcdY” only if it appears as “abc” with no interruptions. “abd” is a subsequence of “abcde” because you can drop “c” and “e” while keeping the order, but it is not a substring because “d” does not immediately follow “b”.
Is there an iterative solution?
Yes. Start with a list containing one empty string. For each character in the input string, iterate over the current list of subsequences and append a version with the new character added. This avoids recursion entirely and produces the same output. The iterative version runs in O(n * 2^n) time and O(n * 2^n) space because the list of subsequences grows exponentially with each character.
How does this relate to bit manipulation?
Each subsequence corresponds to a binary number of n bits where a 1 means include and a 0 means exclude. For a string of length 3, the binary numbers 000 through 111 enumerate all possible subsequences. You can generate subsequences by iterating from 0 to 2^n and checking which bits are set. This is a neat alternative to recursion, though it produces the same results.
