Generate All Subsequences of a String

Problem Generate ALL subsequences of a string — every subset of characters with original order preserved (2^n of them, including the empty one; clarify if empty should be excluded).

Input / Output

• Input: string s. Output: list of all subsequences.

Constraints

• |s| <= ~20 (output is exponential by nature); duplicates in s produce duplicate subsequences — ask whether to dedupe.

Example

• "abc" → ["", "a", "b", "c", "ab", "ac", "bc", "abc"].

Expected approach

• Backtracking: at index i, branch on exclude/include s[i]; emit at i == n. O(2^n · n). Bitmask alternative: for mask in [0, 2^n), pick chars whose bit is set — iterative and easy to reason about. Dedupe via a set or sort+skip if required. Escalations: count distinct subsequences (DP), subsequences matching a predicate — the recursion skeleton is what's evaluated.