Print All Subsequences of a String

Given a string S of lowercase English letters, generate all of its subsequences (including the empty subsequence) using recursion: at each character, first make the recursive call that excludes it, then the call that includes it. Print every subsequence produced by this process, one per line, in the exact order the recursion generates them, with the empty subsequence printed as a blank line.

Input: A single line containing the string S. Output: 2^|S| lines, each containing one subsequence (a blank line for the empty subsequence), in the order described above.

1 <= |S| <= 12. S consists only of lowercase English letters.

The EXACT order of recursive calls (exclude-then-include, consistently at every level) is what produces THIS problem's specific required output order - a different ordering convention (include-then-exclude) would produce a different, equally valid, but non-matching sequence.

Generate every possible subsequence of a string using an include/exclude recursive branching pattern. Brute force: There isn't really a 'slower' alternative here beyond the direct include/exclude recursive branching - this recursive enumeration IS the natural, correct way to generate all 2^n subsequences, since the problem genuinely requires all of them. Optimised: The specific ORDER of recursive calls (exclude before include, at every level) is what determines the EXACT output order this problem requires - recognizing that this ordering choice (not just the branching structure itself) controls the output sequence is the key detail.

1. Write a recursive function f(index, current) where 'current' is the subsequence built so far. 2. At each index, FIRST recurse EXCLUDING the character at that index, THEN recurse INCLUDING it - this fixed order determines the exact output order. 3. The BASE CASE is index == length of S: print whatever 'current' holds (an empty 'current' prints a blank line).

Time: O(2^n * n) - there are 2^n subsequences, and each takes O(n) to build/print, though the small constraint (|S| <= 12) keeps this entirely manageable. Space: O(n) for the recursion stack depth, plus O(2^n * n) if all subsequences are stored before printing.

|S| = 1 produces exactly 2 lines (a blank line, then S itself). |S| = 12 produces 4096 lines and is the largest input this problem is tested with.

Be ready to connect this directly to 'Generate All Subsets Using Bitmasking' from the Bit Manipulation category - both enumerate the exact same 2^n possibilities, just via different mechanisms (recursive branching here, versus iterating bitmask integers there).