Subsets & Permutations

1. Introduction

What are Subsets & Permutations?

Subsets (or Combinations) are combinations of elements chosen from a set. The order of elements does not matter (e.g. [1, 2] is identical to [2, 1]). A set of size N has 2^N possible subsets.

Permutations are arrangements of elements where the order of items is critical (e.g. [1, 2] is a different permutation than [2, 1]). A set of size N has N! permutations.

Why study them?

These problems form the core templates of backtracking. Mastering duplicate avoidance checks in subsets and permutations allows you to solve almost all combination search problems.

---

2. Mental Models

Subsets: The Grocery Shopping List

Imagine walking down a supermarket aisle:

You look at each item one by one from left to right.

For each item, you make a binary choice: Pick it (put it in your shopping cart) or Skip it (leave it on the shelf).

Because you only move forward, you never generate duplicate order combinations like [apples, bananas] and [bananas, apples].

Permutations: Placing Books on a Shelf

Imagine arranging N unique books on a shelf:

For the first slot, you can pick any book from the box.

For the second slot, you can pick any book that is still remaining in the box (tracked by a used checklist array).

Since any book can go in any slot, you generate all possible order arrangements.

---

3. Core Algorithms & Implementations

Deduplication Strategies

To generate unique outputs from datasets containing duplicate values: 1. Subsets II: Sort the input array. During recursion, skip elements if nums[i] == nums[i - 1] and i > start. This ensures that we only try the duplicate value once at the same index level of the decision tree. 2. Permutations II: Sort the input array. Skip elements if nums[i] == nums[i - 1] and !used[i - 1]. This enforces that duplicate values are only processed in a single relative index order.

---

4. Visualizing Duplicate Branch Pruning

Decision tree for Subsets II on sorted array [1, 2, 2]:

When evaluating the loop at the root, the second branch for 2 is pruned (i > start check) because a branch starting with 2 (the first one) has already been fully explored.

---

5. Real-World Examples

Crypto Wallet Seeds: Permuting 12 seed words to recover private keys.

E-Commerce Filter Menus: Generating all possible subsets of checked product features (e.g. price range + color + size combinations).

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers test duplicate bounds:

"Given a string containing letters, print all anagrams." -> Anagrams represent Permutations. Use the used-array template. If duplicate characters are present, use the !used[i-1] skip check.

"Find all unique combinations of size K that sum to target." -> Combination Sum (LeetCode 39/40). This is a subset variant. If elements can be reused, pass i instead of i + 1 to recursive steps.

Common Mistakes

> 2. Wrong index checks for subsets: Using i > 0 instead of i > start to skip duplicates in subsets. This error will prune valid paths like [1, 2, 2] entirely, only outputting single duplicates.

---

7. Summary

Subsets: 2^N options. Use a start index tracking variable to enforce forward-only choices.

Permutations: N! options. Use a used checklist array to allow arbitrary index arrangements.

Deduplication: Sort input arrays. Skip subsets when i > start && nums[i] == nums[i-1]. Skip permutations when i > 0 && nums[i] == nums[i-1] && !used[i-1].

---

8. Quiz

Question 1: What is the time complexity of generating all subsets of a unique array of size N?

Answer: O(N × 2^N) time. There are 2^N subsets, and copying each path into the results list takes O(N) operations.

Question 2: Why do we pass 'i + 1' to the recursive step backtrack(i + 1, path) instead of 'start + 1' in subsets?

Answer: Passing i + 1 ensures that we proceed to the element after the one we just picked. Passing start + 1 would cause elements to be repeated, resulting in infinite loops or duplicate combinations.

Question 3: If an array contains duplicates, what condition must we meet before generating permutations?

Answer: We must sort the array first so that duplicate values are adjacent.

Question 4: True or False: Permutations of size N always require more time to run than subsets of size N.

Answer: True for any reasonable value of N (N ≥ 4). Factorial complexity N! grows significantly faster than exponential complexity 2^N (e.g. for N=10, 2^10 = 1024 whereas 10! = 3,628,800).

Question 5: What is the space complexity of generating permutations?

Answer: O(N) auxiliary space for the recursion stack and the used array.