54. Print All Distinct Subsequences of a String

Given a string s, print all of its distinct non-empty subsequences, sorted in ascending alphabetical order and space-separated on one line.

Input: The input is a single line containing the string s. Output: Print all distinct non-empty subsequences of s, sorted alphabetically and space-separated on one line.

1 <= |s| <= 15

The small constraint (|s| <= 15) is a strong signal that an exponential brute-force enumeration is not just acceptable but the INTENDED approach here - recognizing constraint size as a hint toward the expected algorithmic complexity is a valuable interview skill.

Print every possible way to pick some (or all) characters from a string, keeping their original order, without repeating the same resulting subsequence twice. Brute force: Generate every possible include/exclude combination directly (2^n total combinations for a string of length n) - this is exactly what's needed here, since the problem genuinely wants ALL of them, but duplicates must still be filtered. Optimised: Using a SET (rather than a plain list) to collect the generated subsequences automatically removes exact duplicates that can arise when the string has repeated characters (e.g. 'aab' would otherwise generate the same subsequence 'a' from two different index choices) - sorting the deduplicated set at the very end produces the required alphabetical order.

Enumerate every non-empty bitmask from 1 to 2^n - 1, and for each mask build the subsequence string made of the characters whose bit is set, inserting every resulting string into a hash set to automatically discard duplicates (which arise whenever the string has repeated characters). Once all masks are processed, dump the hash set's contents into a list and sort it alphabetically before printing. This is correct because every subsequence corresponds to exactly one subset of index positions, but it wastes time reconstructing and hashing masks that are guaranteed to be duplicates of ones already seen. Time: O(2^n * n) Space: O(2^n * n)

Use the same include/skip backtracking, but at every recursive call, before branching on 'include character at position i', check a small seen-set scoped to that call to skip any character value already tried as the next pick at this exact recursion point (the classic technique used to generate distinct subsequences even when the string has repeated letters), and insert completed subsequences directly into an ordered set (like a TreeSet) instead of a plain hash set. This way no true duplicate subsequence is ever generated in the first place, and the ordered set keeps results in alphabetical order automatically, removing the need for a separate O(D log D) sort pass over the distinct results at the end. Time: O(2^n * n) worst case, but strictly less redundant work than brute/better Space: O(2^n * n)

Use recursive backtracking that, at each index, branches into 'include this character' and 'skip this character', building up subsequence strings incrementally instead of decoding integer bitmasks. Every complete non-empty string produced along the way is inserted into a hash set for deduplication, then sorted at the end. This keeps the same worst-case cost as brute force but avoids the extra bitmask-decoding step, and the incremental string building lets you prune the empty-string case for free. Time: O(2^n * n) Space: O(2^n * n)

1. For each character in the string, recursively branch into two choices: INCLUDE it in the current subsequence being built, or EXCLUDE it. 2. When you reach the end of the string, if the subsequence built so far is non-empty, record it. 3. Collect all recorded subsequences into a set (to automatically drop exact duplicates), then sort and print them.

Time: O(2^n * n) in the worst case - there are up to 2^n possible subsequences, and each one may take O(n) to build/compare, though the small constraint (|s| <= 15) keeps this entirely manageable. Space: O(2^n * n), for storing all the generated distinct subsequences.

s with repeated characters, where many generated subsequences collapse into fewer distinct ones; s of length 15 with all distinct characters, producing 2^15 - 1 subsequences, testing generation and dedup performance.

Be explicit that the exponential complexity here is UNAVOIDABLE and expected - the problem genuinely asks for an exponential-sized output (all subsequences), so there's no clever trick to avoid the exponential blowup, only to generate and deduplicate it cleanly.