Subsets and Permutations Interview Pattern: When to Use It and 5 Problems to Practice (202

When interviewers ask you to generate every possible grouping of items, they are usually testing your grasp of exponential‑time search. Two closely related patterns cover most of those questions: subsets (also called power set) and permutations. The former cares only about which elements appear, the latter also cares about the order they appear in. Knowing the subtle difference lets you pick the right recursion strategy and avoid wasted time on the wrong data structure.

Spotting the Pattern in a Prompt

If the statement mentions order does not matter or choose any number of elements, think subsets. If it says order matters, arrange, or all possible sequences, you’re dealing with permutations. The presence of a size constraint (e.g., "choose exactly 3") still falls under subsets but adds a pruning condition.

A Worked Example: Subsets of a List

Below is a concise Python implementation using backtracking. It works for any iterable and can be tweaked for a fixed‑size subset.

from typing import List

def subsets(nums: List[int]) -> List[List[int]]:
    result: List[List[int]] = []
    path: List[int] = []

    def backtrack(start: int) -> None:
        # Every recursion level represents a decision point: include or skip.
        result.append(path.copy())  # capture current combination
        for i in range(start, len(nums)):
            path.append(nums[i])          # choose
            backtrack(i + 1)              # explore further
            path.pop()                    # undo choice

    backtrack(0)
    return result


print(subsets([1, 2, 3]))

The function walks the list, at each index deciding whether to pick the element. The start index prevents re‑using earlier items, guaranteeing each subset appears exactly once. The output for [1,2,3] is:

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Complexity

• Time: O(2ⁿ) – each element can be either in or out of a subset, yielding 2ⁿ combinations.
• Space: O(2ⁿ) for the result list, plus O(n) recursion stack.

If you need only subsets of size k, add a guard if len(path) == k: before appending to result and skip the recursive call when len(path) > k.

Permutations: When Order Matters

A classic backtracking skeleton for permutations looks similar but differs in two key ways:

1. The recursion depth equals the length of the input because every position must be filled.
2. We track which elements have already been used.

def permutations(nums: List[int]) -> List[List[int]]:
    result: List[List[int]] = []
    used = [False] * len(nums)
    path: List[int] = []

    def backtrack() -> None:
        if len(path) == len(nums):
            result.append(path.copy())
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result

Complexity

• Time: O(n·n!) – each of the n! permutations is built by n recursive calls.
• Space: O(n·n!) for the output, plus O(n) for the recursion stack and the used array.

Common Pitfalls and How to Avoid Them

1. Duplicate Elements – If the input contains repeats, naive backtracking will produce duplicate subsets or permutations. The fix is to sort the input first and skip a choice when it equals the previous element and the previous element was not used in the current branch.
2. Unnecessary Copying – Frequent path.copy() can be costly. Append the final copy only when you reach a leaf (full subset or permutation) and reuse the same list otherwise.
3. Exponential Blow‑up – Remember that these patterns are inherently exponential. Interviewers often add a constraint (e.g., k‑size subsets, n ≤ 10) to keep the problem tractable. Mention the theoretical bound early; it shows you understand the limits.
4. Misreading the Requirement – If the prompt says "all possible strings" but the input is a list of characters, you still generate permutations of the list and then join each result into a string. Clarify the expected output format before coding.

Five Representative Practice Problems

Below are five problems you can solve on your own or with a mock interview partner. The descriptions avoid copying any copyrighted statements; they focus on the core idea and give a hint for each.

1. Power Set with a Target Sum Goal: Return every subset whose elements sum to a given target. Hint: Use the subset backtracking template, but add a running current_sum variable. Prune the branch when current_sum > target.

2. Unique Permutations of a String with Duplicates Goal: Generate all distinct orderings of a string that may contain repeated characters. Hint: Sort the characters first. In the loop, skip a character if it is the same as the previous one and the previous one has not been used in the current path.

3. Combination Sum III Goal: Find all size‑3 subsets of numbers 1‑9 that add up to a target (e.g., 7). Hint: The classic combination‑sum backtrack works; enforce len(path) == 3 before adding to results.

4. Letter Case Permutation Goal: Given an alphanumeric string, return all strings where each letter can be either uppercase or lowercase. Hint: Treat each character as a binary choice (keep as is, toggle case). Use a backtrack that branches on letters only; digits are passed through unchanged.

5. Restore IP Addresses Goal: Insert three dots into a digit string to form valid IPv4 addresses. Hint: This is a constrained permutation problem: you are arranging three separators. Use backtracking to choose split points, and prune when any segment exceeds 255 or has leading zeros.

How to Practice This

1. Write the Skeleton First – Implement the generic backtrack function (with path, start, and a used array) before adding problem‑specific checks.
2. Add Pruning Early – As soon as you notice a branch cannot possibly satisfy the constraints (e.g., sum too large, duplicate would repeat), return immediately. This keeps the recursion tree small.
3. Run a Mock Interview – Use Call Assistant to record yourself explaining the approach out loud. Play it back to ensure you stay on topic and can articulate why the pattern fits.

---

FAQ

• When should I choose subsets over permutations? Choose subsets when the order of selected items does not affect the answer. If the problem cares about "how many ways to pick" rather than "in what order", subsets are the right tool.

• Can I use iterative solutions instead of recursion? Yes. For subsets, a bit‑mask loop over 0..(1<<n)-1 works. For permutations, the iterative Heap's algorithm is common. However, recursive backtracking is usually clearer in an interview.

• How do I handle large inputs without blowing up memory? Most interview problems limit n to 10‑15 for exponential patterns. If the limit is higher, the problem is likely asking for a combinatorial count rather than enumeration. Clarify the expected output with the interviewer.

• What if the interviewer asks for both subsets and permutations together? Break the problem into two stages: first generate the required subsets, then for each subset run a permutation routine. Explain the combined complexity (often the product of the two individual complexities).