Part 8 · Lesson 33 · read
Subsets and Permutations
Pick or skip each item, to list every possible choice.
On this page
A tree of choices
Lesson 32 drew recursion trees. In this lesson each branch is a decision. For example: use this item or not, which item goes next, or which letter to use. A path from the root to a leaf is one full set of decisions, and the leaves are the answers. To list every subset, permutation or combination, you just walk through the whole tree. (A subset is some of the items. A permutation is all the items in some order. A combination is a group of items where order does not matter.) In one line: [1, 2] and [2, 1] are the same combination, but they are two different permutations.
Every solution in this lesson uses the same three-step move. This is the main idea of backtracking. Backtracking is a method that builds an answer one choice at a time, and when a choice is finished (or fails), it undoes that choice and tries the next one. It is like walking through a maze and coming back to the last turn.
- Choose: add an item to the current
path(the list of choices made so far). - Explore: make a recursive call to decide everything that comes next.
- Un-choose: remove the item with
path.pop(). Then the next choice at the same level starts from the same state.
Pick or skip: all subsets
You build a subset of [1, 2, 3] one element at a time. For each element, you can skip it or pick it. There are 2 choices for each of the n elements, so there are 2n subsets.
function subsets(nums) { const out = []; const path = []; function go(i) { if (i === nums.length) { // we decided about every element: this path is one subset out.push([...path]); // save a copy! path keeps changing return; } go(i + 1); // skip nums[i] path.push(nums[i]); // pick nums[i] go(i + 1); path.pop(); // undo the pick before going back } go(0); return out;}console.log(JSON.stringify(subsets([1, 2]))); // [[],[2],[1],[1,2]]path is one array that every call shares, and it keeps changing. If you write out.push(path), you put the same array in the result many times. At the end, all of them would be empty. Always save a copy: out.push([...path]).The loop form (every node is an answer)
There is a second way to write it. It is more general, and you will use it again for combinations and combination sum. At each call, loop over the items that can come next. You only look at items after the one you just chose (start only moves forward). So you never make the same set in two different orders. In this form, every node of the tree is a valid subset, not just the leaves.
function subsets(nums) { const out = []; const path = []; function go(start) { out.push([...path]); // every node of the tree is a subset for (let i = start; i < nums.length; i++) { path.push(nums[i]); // choose go(i + 1); // explore: use only later elements, so no repeats path.pop(); // un-choose (undo) } } go(0); return out;}console.log(JSON.stringify(subsets([1, 2, 3]))); // [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]Traced: subsets of [1, 2, 3]
path holds the choices made so far. out collects every subset.
1const nums = [1, 2, 3];▶const out = [], path = [];3function go(start) {4 out.push([...path]);5 for (let i = start; i < nums.length; i++) {6 path.push(nums[i]);7 go(i + 1);8 path.pop();9 }10}11go(0);12console.log(out);| nums | [1, 2, 3] |
| out | [] |
| path | [] |
| Call go(start) | Saves | Then chooses… |
|---|---|---|
| go(0), path [] | [] | 1, then 2, then 3 |
| go(1), path [1] | [1] | 2, then 3 |
| go(2), path [1, 2] | [1, 2] | 3 |
| go(3), path [1, 2, 3] | [1, 2, 3] | (nothing left) |
| go(3), path [1, 3] | [1, 3] | (nothing left) |
| go(2), path [2] | [2] | 3 |
| go(3), path [2, 3] | [2, 3] | (nothing left) |
| go(3), path [3] | [3] | (nothing left) |
Eight calls and eight subsets: 2³.
Subsets with duplicates
Take [1, 2, 2]. If you pick the first 2, or pick the second 2, you get the same subset [1, 2]. The fix has two parts. First, sort the array, so equal values sit next to each other. Second, inside the loop, skip a value that is equal to the one before it at the same level. The condition is i > start && nums[i] === nums[i − 1]. The first 2 at this level is allowed, because it is at i === start. Later copies of 2 at the same level are skipped.
function subsetsWithDup(nums) { nums = [...nums].sort((a, b) => a - b); // equal values must sit next to each other const out = [], path = []; function go(start) { out.push([...path]); for (let i = start; i < nums.length; i++) { if (i > start && nums[i] === nums[i - 1]) continue; // we already tried this same value at THIS level path.push(nums[i]); go(i + 1); path.pop(); } } go(0); return out;}console.log(JSON.stringify(subsetsWithDup([1, 2, 2]))); // [[],[1],[1,2],[1,2,2],[2],[2,2]]Permutations
A permutation uses every element exactly once, in some order. At each step, any element that is not in the path yet may come next. So the loop starts from 0 every time, and a used array remembers which elements are taken. There are n! leaves. (n! means n × (n − 1) × … × 1. For example, 3! = 6.)
function permute(nums) { const out = [], path = []; const used = new Array(nums.length).fill(false); // which elements are already in the path function go() { if (path.length === nums.length) { out.push([...path]); return; } for (let i = 0; i < nums.length; i++) { // any element not used yet may come next if (used[i]) continue; used[i] = true; path.push(nums[i]); go(); path.pop(); used[i] = false; } } go(); return out;}console.log(JSON.stringify(permute([1, 2, 3]))); // [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Combinations of size k
Choose k numbers out of 1…n. The order does not matter. This is the subset loop with two changes. First, stop when the path has length k, because that is an answer. Second, prune (cut off) branches that cannot reach k. If there are not enough numbers left, do not go further.
function combine(n, k) { const out = [], path = []; function go(start) { if (path.length === k) { out.push([...path]); return; } // prune (cut off a branch): there must be enough numbers left (k - path.length) to fill the path for (let i = start; i <= n - (k - path.length) + 1; i++) { path.push(i); go(i + 1); path.pop(); } } go(1); return out;}console.log(JSON.stringify(combine(4, 2))); // [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]Letter combinations of a phone number
On a phone keypad, each digit has some letters (2 → abc, 3 → def …). If you type “23”, you can spell any letter of the first digit followed by any letter of the second. The tree has one level for each digit and one child for each letter.
function letterCombinations(digits) { if (digits === "") return []; const letters = { 2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz" }; const out = []; function go(i, path) { if (i === digits.length) { out.push(path); return; } for (const ch of letters[digits[i]]) go(i + 1, path + ch); // one child for each letter of this digit } go(0, ""); return out;}console.log(JSON.stringify(letterCombinations("23"))); // ["ad","ae","af","bd","be","bf","cd","ce","cf"]console.log(JSON.stringify(letterCombinations(""))); // []How many answers? The cost of generating them
| Problem | Number of answers | Time (including copying each answer) |
|---|---|---|
| subsets of n items | 2ⁿ | O(n · 2ⁿ) |
| permutations of n items | n! | O(n · n!) |
| combinations C(n, k) | n! / (k! (n − k)!) | O(k · C(n, k)) |
| letter combinations of d digits | up to 4ᵈ | O(d · 4ᵈ) |
These take exponential time (the work multiplies by a fixed factor, such as 2, for every extra item) because the answer itself is very large. You cannot be faster than the size of the output. This is why these problems only have small inputs (roughly n ≤ 20 for subsets and n ≤ 10 for permutations).
Practice questions
Before you write code for each one, draw the tree for an input with 3 elements. Write down what each level decides.
Return all possible subsets of an array of different integers. (A subset is any group of the items, including the empty group and the whole array.) The result must not contain the same subset twice.
Hint 1
Hint 2
path array. Choose, make the recursive call, then pop (undo). Save a copy of the path.Show all 3 solutions with explanations
At index i, first make the recursive call without nums[i], then make it again with nums[i]. When i = n, save the path.
function subsets(nums) { const out = [], path = []; function go(i) { if (i === nums.length) { out.push([...path]); return; } go(i + 1); path.push(nums[i]); go(i + 1); path.pop(); } go(0); return out;}console.log(JSON.stringify(subsets([1, 2, 3]))); // [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]console.log(subsets([0]).length); // 2There are 2n leaves, and each one is copied in O(n). So the time is O(n · 2n).
Save the path at the start of every call. Then loop over the later elements.
function subsets(nums) { const out = [], path = []; function go(start) { out.push([...path]); for (let i = start; i < nums.length; i++) { path.push(nums[i]); go(i + 1); path.pop(); } } go(0); return out;}console.log(JSON.stringify(subsets([1, 2, 3]))); // [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]The cost is the same. You will use this shape again for combinations and combination sum.
Start with [[]]. For each element, make a copy of every subset you already have and add the element to each copy.
function subsets(nums) { let out = [[]]; for (const x of nums) { out = out.concat(out.map((s) => [...s, x])); } return out;}console.log(JSON.stringify(subsets([1, 2, 3]))); // [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]There is no recursion at all. The number of subsets doubles with each element. It is neat for small inputs.
Learn the first two well, because they work for harder problems too. The third is a nice extra. (LeetCode 78.)
Return all possible subsets of an array that may have repeated values. The result must not have the same subset twice.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Sort the array and make every subset. Turn each subset into a string and keep it in a Set, so a repeat is ignored.
function subsetsWithDup(nums) { nums = [...nums].sort((a, b) => a - b); const seen = new Set(), out = [], path = []; function go(start) { const key = path.join(","); if (!seen.has(key)) { seen.add(key); out.push([...path]); } for (let i = start; i < nums.length; i++) { path.push(nums[i]); go(i + 1); path.pop(); } } go(0); return out;}console.log(JSON.stringify(subsetsWithDup([1, 2, 2]))); // [[],[1],[1,2],[1,2,2],[2],[2,2]]The answer is correct, but some work is wasted. The duplicate branches are still explored before they are thrown away.
Sort the array. Inside the loop, use continue (skip to the next turn) when i > start and the value is equal to the one before it.
function subsetsWithDup(nums) { nums = [...nums].sort((a, b) => a - b); const out = [], path = []; function go(start) { out.push([...path]); for (let i = start; i < nums.length; i++) { if (i > start && nums[i] === nums[i - 1]) continue; path.push(nums[i]); go(i + 1); path.pop(); } } go(0); return out;}console.log(JSON.stringify(subsetsWithDup([1, 2, 2]))); // [[],[1],[1,2],[1,2,2],[2],[2,2]]console.log(JSON.stringify(subsetsWithDup([4, 4, 4, 1, 4]))); // [[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]]The duplicate branches are never entered. Why i > start? The first copy at a level is a new choice. Only the later copies repeat it.
Use the second one. You need the same pattern for Combination Sum II in the next lesson. (LeetCode 90.)
Return all permutations of an array of different integers.
Hint 1
Hint 2
Show all 2 solutions with explanations
Loop over all indexes and skip the used ones. Choose, make the recursive call, then undo the choice.
function permute(nums) { const out = [], path = []; const used = new Array(nums.length).fill(false); function go() { if (path.length === nums.length) { out.push([...path]); return; } for (let i = 0; i < nums.length; i++) { if (used[i]) continue; used[i] = true; path.push(nums[i]); go(); path.pop(); used[i] = false; } } go(); return out;}console.log(JSON.stringify(permute([1, 2, 3]))); // [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]console.log(permute([0, 1, 2, 3]).length); // 24There are n! leaves, and each one is copied in O(n). So the time is O(n · n!) and the extra space is O(n).
For position i, swap each later element into it one by one. Make the recursive call for i + 1, then swap back. You do not need a used array.
function permute(nums) { const out = []; const a = [...nums]; function go(i) { if (i === a.length) { out.push([...a]); return; } for (let j = i; j < a.length; j++) { [a[i], a[j]] = [a[j], a[i]]; // choose a[j] for position i go(i + 1); [a[i], a[j]] = [a[j], a[i]]; // undo } } go(0); return out;}console.log(JSON.stringify(permute([1, 2, 3]))); // [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]There are the same number of answers, but they come in a slightly different order. The array itself works as the path.
The used-array version is easier to change for harder problems (see Permutations II). (LeetCode 46.)
Return all combinations of k numbers chosen from 1 … n.
Hint 1
Hint 2
Hint 3
Show the solution with explanations
Loop i from start up to n − (k − path.length) + 1. A later start cannot fill all k places.
function combine(n, k) { const out = [], path = []; function go(start) { if (path.length === k) { out.push([...path]); return; } for (let i = start; i <= n - (k - path.length) + 1; i++) { path.push(i); go(i + 1); path.pop(); } } go(1); return out;}console.log(JSON.stringify(combine(4, 2))); // [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]console.log(JSON.stringify(combine(1, 1))); // [[1]]console.log(combine(5, 3).length); // 10There are C(n, k) answers. Without the smaller loop limit, the code is still correct, but it goes down many dead ends (branches that give no answer).
(LeetCode 77.)
You get a string of digits from 2 to 9. Return every letter combination that these digits could spell on a phone keypad.
Hint 1
Hint 2
[""].Show all 2 solutions with explanations
At digit i, loop over its letters. For each letter, make the recursive call with that letter added to the string.
function letterCombinations(digits) { if (digits === "") return []; const map = { 2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz" }; const out = []; function go(i, path) { if (i === digits.length) { out.push(path); return; } for (const ch of map[digits[i]]) go(i + 1, path + ch); } go(0, ""); return out;}console.log(JSON.stringify(letterCombinations("23"))); // ["ad","ae","af","bd","be","bf","cd","ce","cf"]console.log(JSON.stringify(letterCombinations(""))); // []console.log(letterCombinations("79").length); // 16Strings cannot be changed after they are made (they are immutable). So path + ch makes a new string for each child, and you do not need an undo step.
Start with [""]. For each digit, replace every string with new strings, one for each letter of that digit added at the end.
function letterCombinations(digits) { if (digits === "") return []; const map = { 2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz" }; let out = [""]; for (const d of digits) { const next = []; for (const prefix of out) for (const ch of map[d]) next.push(prefix + ch); out = next; } return out;}console.log(JSON.stringify(letterCombinations("23"))); // ["ad","ae","af","bd","be","bf","cd","ce","cf"]It is the same O(d · 4d) work, but with loops instead of recursion.
(LeetCode 17.)
Return all different permutations of an array that may have repeated values.
Hint 1
Hint 2
Show all 2 solutions with explanations
Use the used array. When nums[i] === nums[i − 1] and !used[i − 1], skip this value.
function permuteUnique(nums) { nums = [...nums].sort((a, b) => a - b); const out = [], path = []; const used = new Array(nums.length).fill(false); function go() { if (path.length === nums.length) { out.push([...path]); return; } for (let i = 0; i < nums.length; i++) { if (used[i]) continue; if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue; // we already tried this same value here used[i] = true; path.push(nums[i]); go(); path.pop(); used[i] = false; } } go(); return out;}console.log(JSON.stringify(permuteUnique([1, 1, 2]))); // [[1,1,2],[1,2,1],[2,1,1]]console.log(permuteUnique([2, 2, 1, 1]).length); // 6This condition makes equal values appear only in their original left-to-right order. That removes the repeated orderings.
Keep a Map from each value to how many copies are left. At each step, choose a value (not an index). Because of this, a repeated answer can never be made.
function permuteUnique(nums) { const count = new Map(); for (const x of nums) count.set(x, (count.get(x) || 0) + 1); const out = [], path = []; function go() { if (path.length === nums.length) { out.push([...path]); return; } for (const [value, left] of count) { if (left === 0) continue; count.set(value, left - 1); path.push(value); go(); path.pop(); count.set(value, left); } } go(); return out;}console.log(JSON.stringify(permuteUnique([1, 1, 2]))); // [[1,1,2],[1,2,1],[2,1,1]]This is often easier to understand than the sort-and-skip condition.
Either one works. (LeetCode 47.)
You get n pairs of parentheses (round brackets). Return every combination that is well-formed, which means every opening bracket has a matching closing bracket.
Hint 1
Hint 2
Show all 2 solutions with explanations
Build every string of 2n characters. Then keep only the balanced ones (every opening bracket has a closing bracket).
function generateParenthesis(n) { const valid = (s) => { let open = 0; for (const c of s) { open += c === "(" ? 1 : -1; if (open < 0) return false; } return open === 0; }; const out = []; (function go(s) { if (s.length === 2 * n) { if (valid(s)) out.push(s); return; } go(s + "("); go(s + ")"); })(""); return out;}console.log(JSON.stringify(generateParenthesis(2))); // ["(())","()()"]22n strings are built and checked. That is far too many when n gets bigger.
Count how many opening and closing brackets you have used. Add “(” if opens < n. Add “)” if closes < opens.
function generateParenthesis(n) { const out = []; function go(s, open, close) { if (s.length === 2 * n) { out.push(s); return; } if (open < n) go(s + "(", open + 1, close); if (close < open) go(s + ")", open, close + 1); // never close more brackets than are open } go("", 0, 0); return out;}console.log(JSON.stringify(generateParenthesis(3))); // ["((()))","(()())","(())()","()(())","()()()"]console.log(generateParenthesis(4).length); // 14Every start of a string that we build is already valid, so every leaf is an answer. The count is a Catalan number (a famous counting sequence: 1, 2, 5, 14, 42, ... for n = 1, 2, 3, 4, 5). The idea “only add choices that are valid” is the main idea of the next lesson.
Use the second approach. (LeetCode 22.)
| The question says… | Loop | Starts at | Save when… |
|---|---|---|---|
| all subsets | for i from start | start | every call |
| combinations of size k | for i from start | start | path.length === k |
| all orderings (permutations) | for every i, skip used | 0 | path.length === n |
| one choice for each level (phone letters) | for each option of this level | — | level === last |
| duplicates in the input | sort, then skip equal values at the same level | same as above | same as above |
Make it stick
- Write the choose, explore, un-choose pattern. Explain why you must copy the path when you save it.
- Write the loop-form subsets function. Explain why
startonly moves forward. - Explain the duplicate-skipping condition
i > start && nums[i] === nums[i − 1]. - Say how many subsets, permutations and combinations there are. Explain why the running time is at least that large.
Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.
What's next
Everything in this lesson lists all the answers. Lesson 34 adds a rule: you make only the answers that are valid, and you stop a branch as soon as you know it cannot work. The problems are combination sum, palindrome partitioning, word search and N-Queens.
Practise on LeetCode
Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.
Published by Jainik · Last updated · How these lessons are made
Keep learning
Part of the study guide
Related series