Print the power set of a string of distinct characters
Filed under Paytm
Confirm characters are distinct, whether the empty subset is included, and whether order inside a subset must follow the original string (it does).
The question
Given a string of distinct characters such as 'abc', print or return all of its subsets (the power set), including the empty string. Use recursion and be ready to draw the recursion tree.
Constraints
- 1 <= len(s) <= 15
- All characters are distinct
Examples
- Input
- s = 'abc'
- Output
- '', a, b, c, ab, ac, bc, abc
- Why
- Eight subsets, 2^3, each character either taken or skipped.
Approach
Confirm characters are distinct, whether the empty subset is included, and whether order inside a subset must follow the original string (it does).
Iterate masks 0 to 2^n - 1 and build a subset from the set bits. Correct and iterative; the interviewer asked for recursion, so use this as a cross-check.
go(i, cur): if i equals n, record cur. Otherwise call go(i+1, cur) to skip s[i] and go(i+1, cur + s[i]) to take it. The tree has depth n and 2^n leaves, one per subset.
Root is (0, ''); each node splits into 'skip' and 'take' children down to level n. Check n = 0 (one empty subset), n = 1, and that strings built by concatenation do not share state between branches.
Solution
O(n * 2^n) time, O(n) recursion depth plus output
def power_set(s):
res = []
def go(i, cur):
if i == len(s):
res.append(cur)
return
go(i + 1, cur) # skip s[i]
go(i + 1, cur + s[i]) # take s[i]
go(0, "")
return res
Tips
- What they are testing: Clear recursive thinking and being able to visualise the recursion tree, including recovering from a bug.
- Common mistake: Passing a shared mutable buffer without undoing the choice after the recursive call, so subsets leak into each other.
Follow-ups
- After an error was found in the code, rewrite it and redraw the recursion tree.
Related Paytm questions
Collected from public candidate posts and coding forums. Updated Nov 2026.