DSA interview question

All Subsequences of a String (the Pick / Skip Pattern)

Easy · Algorithms · Topics: recursion, theory

The problem

A search engine's autocomplete test generates every subsequence of a query string (characters in their original order, not necessarily contiguous) to check fuzzy matching. For "abc" that's abc, ab, ac, a, bc, b, c and the empty string: 2ⁿ in total. This is the template behind a whole family of recursion problems. At each index, decide whether to pick the character or skip it, and act when the index reaches the end. Small changes to that template give "print all subsequences with property P", "stop at the first one found" (return a bool), and "count them" (return a number).

Example: "abc" → "abc" "ab" "ac" "a" "bc" "b" "c" "".

Function signature

vector<string> allSubsequences(const string& s);  // pick-then-skip order; 2^n strings

Test cases

Input	Output (pick-then-skip order)	Explanation
`"abc"`	`"abc" "ab" "ac" "a" "bc" "b" "c" ""`	2³ = 8
`"ab"`	`"ab" "a" "b" ""`
`"aa"`	`"aa" "a" "a" ""`	Different positions, so both copies of `"a"` appear
`"a"`	`"a" ""`
`""`	`""`	Only the empty subsequence

(Confirm: a subsequence keeps the original order; the empty subsequence counts; duplicates from repeated characters are kept.)

How interviewers phrase it

"Print all subsequences of a string" (the power set of a string).
It's usually the warm-up before "print, find one, or count the subsequences whose sum is K".

Clarifying questions to ask

Subsequence (order kept, gaps allowed) or substring (contiguous)?
Should the empty subsequence be included?
Should duplicates caused by repeated characters be removed?

Follow-ups to expect

"Pattern 1, print all with a property:"
"Pattern 2, print only one:"
"Pattern 3, count them:"
"Complexity?"
"Iterative alternative?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview