โ† Paytm questions
CodingReported in a candidate post, Sep 2021

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

  1. Confirm characters are distinct, whether the empty subset is included, and whether order inside a subset must follow the original string (it does).

Solution

O(n * 2^n) time, O(n) recursion depth plus output

Python
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.