What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Backtracking & State Search

Builds on Subsets, which you haven’t finished yet.

P2MediumBuilt on Subsets~6 min speedrun

Built on

SubsetsA used array replaces start, so any element not yet in path can come next, and each element is used once.

Grows into

Constraint Backtracking

The problem

Permutations (LC 46)(opens leetcode.com)

Given an array nums of distinct integers, return every possible ordering of all its elements -- i.e., every permutation -- in any order.

A permutation uses each element from nums exactly once, arranged into some linear sequence.

Example 1

Input:nums = [1,2,3]

Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Three distinct numbers can be ordered in 3 * 2 * 1 = 6 ways.

Permutations

elements ➔ unused candidate selection ➔ boolean visited array

Spot it when: Order matters and every element is used exactly once: arrangements, orderings, assigning people to seats.

Permutations

Python

1	from typing import Callable, List, TypeVar
2
3	Item = TypeVar("Item")
4
5
6	def permutations(items: List[Item], can_place: Callable[[List[Item], Item], bool]) -> List[List[Item]]:
7	"""Permutations: every ordering of items, each position filled with an item that is not in path yet.
8	can_place(path, item) says whether item may come next after path. It prunes a branch early.
9	Precondition: equal items count as different items, so equal values give repeated orderings.
10	For equal values (Permutations II), sort the values and pass (value, index) pairs.
11	Then skip a pair when the equal pair just before it is not in path yet.
12	N = len(items). T = the cost of one can_place call.
13	Time: O(N * N! * T) \| Space: O(N) path + recursion stack, output not counted
14	"""
15	results: List[List[Item]] = []
16	path: List[Item] = []
17	used = [False] * len(items) # used[i] is true exactly when items[i] is in path
18
19	def backtrack() -> None:
20	# 1. Save a Full Ordering:
21	# path only counts as one ordering once it holds every item, so stop and save
22	# it there; a shorter path is still missing items and is not a real answer.
23	if len(path) == len(items):
24	results.append(list(path))
25	return
26
27	for i in range(len(items)):
28	# 2. Offer Every Unused Item:
29	# The loop restarts at 0 every call, so any item not already in path may
30	# come next; used[i] and can_place rule out the ones that cannot.
31	if used[i] or not can_place(path, items[i]):
32	continue
33
34	# 3. Choose, Explore, Un-choose:
35	# Mark items[i] used and append it, recurse so the next position sees it
36	# taken, then undo both marks so a later i in this loop can still use it.
37	used[i] = True
38	path.append(items[i])
39	backtrack()
40	path.pop()
41	used[i] = False
42
43	backtrack()
44	return results

Invariant: used[i] is true exactly when nums[i] is in path, so path never holds the same element twice.

Every position may hold any element that is not already in path, so the loop always starts at 0 and skips i when used[i] is true. Mark used[i] and append before backtrack(), then pop and unmark after it: each full path is then a different sequence of choices, and with distinct values a different ordering, so every ordering is saved exactly once when len(path) == len(nums). The trap is the undo: forget used[i] = False after the call and every later branch treats that element as taken, so most orderings never appear.

See it run

Permutations, step by step

path []saved 0

The top row is nums. The middle row is used. The bottom row is path, filled from the left.

i the index the loop is looking at
used[i] the used flag that is read or set to True
path the slot just added to path
undo the slot or flag just reset by the undo

nums is [1, 2]. path is empty, and every used[i] is False.

nums

used

False

path

1 / 18

Gotchas1 of 4

The trap
Gotcha 1: Leaving out used[i] = False after the recursive call
Mistake
```
path.pop()
```
Fix
```
path.pop()
used[i] = False
```
What happens: used[i] becomes True when nums[i] is placed. Without the reset, it stays True after the branch returns. Every later branch then skips nums[i]. So only the first ordering is saved.
Example: nums = [1, 2]
Mistake: returns [[1, 2]]Fix: returns [[1, 2], [2, 1]]
Gotcha 2: Saving path before it holds every element
Mistake
```
results.append(list(path))
```
Fix
```
if len(path) == len(nums):
    results.append(list(path))
    return
```
What happens: Subsets (LC 78) saves path at every node. A permutation must use every element, so it is ready only when len(path) == len(nums). Saving at every node also saves the empty list and every shorter path.
Example: nums = [1, 2]
Mistake: returns [[], [1], [1, 2], [2], [2, 1]]Fix: returns [[1, 2], [2, 1]]
Gotcha 3: Using this search when n is larger than about 10
What happens: The search builds every ordering, and each full ordering costs O(n) to copy. So the time is O(n · n!). n = 10 gives 3,628,800 orderings. n = 12 gives 479,001,600 orderings, which is too many to list. Check the constraints before you choose this search.
Gotcha 4: Checking the rule only after the ordering is complete
Mistake
```
if len(path) == n and all(v % p == 0 or p % v == 0 for p, v in enumerate(path, 1)):
    count += 1
```
Fix
```
if not used[v] and (v % pos == 0 or pos % v == 0):
```
What happens: Beautiful Arrangement (LC 526) has a rule for each position. Checking it only on a full ordering builds all n! orderings first. The count is the same, but the search is much slower. Test the rule when you place each number v at position pos, counted from 1. A number that breaks the rule then cuts its whole branch at once.

Not this one if…

Order does not matter, as in Combinations (LC 77): [1, 2] and [2, 1] are the same answer, so listing every ordering returns duplicates. See Combinations

Deep Dive

What changes from Subsets: the loop restarts at 0

The Subsets card builds each group in index order, so its loop starts at start. A permutation is an ordering, so [1, 2] and [2, 1] are two different answers. Every position may hold any item that is not in path yet.

So the loop starts at 0 in every call, and a used array records which items are already in path. The loop skips i when used[i] is True.

A permutation must use every item. For this reason the code saves only when len(path) == len(nums). Saving at every node, as Subsets does, would also save the shorter lists.

Why each ordering appears exactly once

At the first position, the loop offers all N items. At the second position, it offers the N - 1 items that are not used. At the third position, it offers N - 2, and so on. The number of full paths is N * (N - 1) * ... * 1, which is N!.

Two different full paths differ at the first position where the loop picked a different index. Each full path ends the walk at its own leaf, so no ordering is saved twice. Each ordering of different values is reachable by one sequence of picks, so none is missed.

For nums = [1, 2, 3], the result has 6 orderings, and backtrack runs 16 times: 1 first call, 3 at depth 1, 6 at depth 2 and 6 at depth 3.

Why the undo has two lines

Take nums = [1, 2]. Choosing does two things: used[i] = True and path.append(nums[i]). So undoing must also do two things: path.pop() and used[i] = False.

The board shows both lines as two steps. The first pop returns path to [1], but used[1] is still True. Only the second line makes nums[1] available again.

Without used[i] = False, permute([1, 2]) returns [[1, 2]], not [[1, 2], [2, 1]]. After the first branch, used[0] and used[1] both stay True, so the second branch has nothing to place.

The cost, and repeated values

There are N! leaves, and saving each one copies path in O(N). The time is O(N * N!). The space is O(N) for path, used and the recursion stack. The output is not counted.

For N = 10, there are 3,628,800 orderings. For N = 12, there are 479,001,600, which is too many to list. Check the limit on N before you choose this search.

The card's precondition says equal values count as different items. For [1, 1, 2], the search returns 6 orderings, but only 3 are different. Permutations II (LC 47) removes the repeats: sort nums, then skip i when i > 0, nums[i] == nums[i - 1] and used[i - 1] is False. That makes equal values enter path from left to right, so each different ordering is saved once.

60-Second Pitch

"Order matters and every item is used once, so each position may hold any item that is not in path. The loop starts at 0 in every call, and used[i] marks the items already placed. I choose by setting used[i] = True and appending to path. I recurse, then I undo both: path.pop() and used[i] = False. I save a copy of path when its length equals len(nums). There are N! orderings and each copy costs O(N), so the time is O(N * N!). The space is O(N). I would prune with a rule check when I place an item, if the problem has such a rule."

Common Questions

How is this different from Subsets (LC 78)?: Subsets builds each group in index order, so its loop starts at start and it saves at every node. Permutations restarts the loop at 0 in every call, uses used to avoid repeating an item, and saves only when path has all the items.
What are the time and space complexity?: O(N * N!) time, because there are N! leaves and each copy costs O(N). The space is O(N) for path, used and the recursion stack. The output is not counted.
What happens if the input has equal values?: Equal values count as different items, so the same ordering is saved several times. For [1, 1, 2], the search returns 6 orderings and only 3 are different. Permutations II (LC 47) sorts nums and skips i when i > 0, nums[i] == nums[i - 1] and used[i - 1] is False.
Could you swap items in place instead of using used?: Yes. You can swap nums[start] with nums[i], recurse on start + 1, and swap back. It uses no used array. The undo is still required, and with equal values the repeat check is harder, so the used version is easier to get right in an interview.
How do you cut the search when the problem has a rule?: Test the rule when you place an item, before backtrack() runs. In Beautiful Arrangement (LC 526), a number that breaks the rule at its position is not placed, so the whole branch below it is never built.

SWE Reasoning

Spot it

The statement asks for all arrangements, orderings or assignments, and the order of the answer matters.
Every item is used exactly once, so a full answer has length len(nums).
A rule can reject a placement early, for example a number must or must not stand at a given position, as in Beautiful Arrangement (LC 526).
The input is small, usually 8 to 10 items, because the answer has N! orderings.
You can say: for this position, which items are still free?

The invariant, step by step

backtrack() starts. If len(path) == len(nums), it saves list(path) and returns.
Otherwise the loop runs i from 0 to the end. If used[i] is True, then nums[i] is already in path, so continue skips it.
For a free i, the code sets used[i] = True and runs path.append(nums[i]). The invariant holds: used[i] is True exactly when nums[i] is in path.
backtrack() fills the remaining positions with the items that are still free.
path.pop() and used[i] = False restore both. path and used are now as they were before step 3, so the next i sees a correct state.
The picks form a choice for each position, so each full path is a different ordering and is saved once.

Traps

No used[i] = False after the call. The flag stays True after its branch returns, so every later branch skips that item. permute([1, 2]) returns [[1, 2]].
Saving at every node. A permutation needs all items. Saving at every call also saves [] and every shorter list. permute([1, 2]) returns [[], [1], [1, 2], [2], [2, 1]].
Saving path and not list(path). The code saves one list object and keeps changing it, so the saved lists are all empty at the end.
Checking the rule only on a full ordering. In Beautiful Arrangement (LC 526), the rule belongs to each position. Test it when you place the number, so a bad number cuts its whole branch. Testing at the end still builds all n! orderings.
A large N. N = 12 needs about 479 million orderings. Read the constraints first.

Practice

Canonical LeetCode:Permutations (LC 46)Permutations II (LC 47)Beautiful Arrangement (LC 526)Number of Squareful Arrays (LC 996)Maximum Compatibility Score Sum (LC 1947)Palindrome Permutation II (LC 267)

Theory Context•Backtracking & State Search

Builds on Subsets, which you haven’t finished yet.

P2MediumBuilt on Subsets~6 min speedrun

Built on

SubsetsA used array replaces start, so any element not yet in path can come next, and each element is used once.

Grows into

Constraint Backtracking

The problem

Permutations (LC 46)(opens leetcode.com)

Given an array nums of distinct integers, return every possible ordering of all its elements -- i.e., every permutation -- in any order.

A permutation uses each element from nums exactly once, arranged into some linear sequence.

Example 1

Input:nums = [1,2,3]

Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Three distinct numbers can be ordered in 3 * 2 * 1 = 6 ways.

Permutations

elements ➔ unused candidate selection ➔ boolean visited array

Spot it when: Order matters and every element is used exactly once: arrangements, orderings, assigning people to seats.

Permutations

Python

1	from typing import Callable, List, TypeVar
2
3	Item = TypeVar("Item")
4
5
6	def permutations(items: List[Item], can_place: Callable[[List[Item], Item], bool]) -> List[List[Item]]:
7	"""Permutations: every ordering of items, each position filled with an item that is not in path yet.
8	can_place(path, item) says whether item may come next after path. It prunes a branch early.
9	Precondition: equal items count as different items, so equal values give repeated orderings.
10	For equal values (Permutations II), sort the values and pass (value, index) pairs.
11	Then skip a pair when the equal pair just before it is not in path yet.
12	N = len(items). T = the cost of one can_place call.
13	Time: O(N * N! * T) \| Space: O(N) path + recursion stack, output not counted
14	"""
15	results: List[List[Item]] = []
16	path: List[Item] = []
17	used = [False] * len(items) # used[i] is true exactly when items[i] is in path
18
19	def backtrack() -> None:
20	# 1. Save a Full Ordering:
21	# path only counts as one ordering once it holds every item, so stop and save
22	# it there; a shorter path is still missing items and is not a real answer.
23	if len(path) == len(items):
24	results.append(list(path))
25	return
26
27	for i in range(len(items)):
28	# 2. Offer Every Unused Item:
29	# The loop restarts at 0 every call, so any item not already in path may
30	# come next; used[i] and can_place rule out the ones that cannot.
31	if used[i] or not can_place(path, items[i]):
32	continue
33
34	# 3. Choose, Explore, Un-choose:
35	# Mark items[i] used and append it, recurse so the next position sees it
36	# taken, then undo both marks so a later i in this loop can still use it.
37	used[i] = True
38	path.append(items[i])
39	backtrack()
40	path.pop()
41	used[i] = False
42
43	backtrack()
44	return results

Invariant: used[i] is true exactly when nums[i] is in path, so path never holds the same element twice.

See it run

Permutations, step by step

path []saved 0

The top row is nums. The middle row is used. The bottom row is path, filled from the left.

i the index the loop is looking at
used[i] the used flag that is read or set to True
path the slot just added to path
undo the slot or flag just reset by the undo

nums is [1, 2]. path is empty, and every used[i] is False.

nums

used

False

path

1 / 18

Gotchas1 of 4

The trap
Gotcha 1: Leaving out used[i] = False after the recursive call
Mistake
```
path.pop()
```
Fix
```
path.pop()
used[i] = False
```
What happens: used[i] becomes True when nums[i] is placed. Without the reset, it stays True after the branch returns. Every later branch then skips nums[i]. So only the first ordering is saved.
Example: nums = [1, 2]
Mistake: returns [[1, 2]]Fix: returns [[1, 2], [2, 1]]
Gotcha 2: Saving path before it holds every element
Mistake
```
results.append(list(path))
```
Fix
```
if len(path) == len(nums):
    results.append(list(path))
    return
```
What happens: Subsets (LC 78) saves path at every node. A permutation must use every element, so it is ready only when len(path) == len(nums). Saving at every node also saves the empty list and every shorter path.
Example: nums = [1, 2]
Mistake: returns [[], [1], [1, 2], [2], [2, 1]]Fix: returns [[1, 2], [2, 1]]
Gotcha 3: Using this search when n is larger than about 10
What happens: The search builds every ordering, and each full ordering costs O(n) to copy. So the time is O(n · n!). n = 10 gives 3,628,800 orderings. n = 12 gives 479,001,600 orderings, which is too many to list. Check the constraints before you choose this search.
Gotcha 4: Checking the rule only after the ordering is complete
Mistake
```
if len(path) == n and all(v % p == 0 or p % v == 0 for p, v in enumerate(path, 1)):
    count += 1
```
Fix
```
if not used[v] and (v % pos == 0 or pos % v == 0):
```
What happens: Beautiful Arrangement (LC 526) has a rule for each position. Checking it only on a full ordering builds all n! orderings first. The count is the same, but the search is much slower. Test the rule when you place each number v at position pos, counted from 1. A number that breaks the rule then cuts its whole branch at once.

Not this one if…

Order does not matter, as in Combinations (LC 77): [1, 2] and [2, 1] are the same answer, so listing every ordering returns duplicates. See Combinations

Deep Dive

What changes from Subsets: the loop restarts at 0

So the loop starts at 0 in every call, and a used array records which items are already in path. The loop skips i when used[i] is True.

A permutation must use every item. For this reason the code saves only when len(path) == len(nums). Saving at every node, as Subsets does, would also save the shorter lists.

Why each ordering appears exactly once

For nums = [1, 2, 3], the result has 6 orderings, and backtrack runs 16 times: 1 first call, 3 at depth 1, 6 at depth 2 and 6 at depth 3.

Why the undo has two lines

Take nums = [1, 2]. Choosing does two things: used[i] = True and path.append(nums[i]). So undoing must also do two things: path.pop() and used[i] = False.

The board shows both lines as two steps. The first pop returns path to [1], but used[1] is still True. Only the second line makes nums[1] available again.

Without used[i] = False, permute([1, 2]) returns [[1, 2]], not [[1, 2], [2, 1]]. After the first branch, used[0] and used[1] both stay True, so the second branch has nothing to place.

The cost, and repeated values

There are N! leaves, and saving each one copies path in O(N). The time is O(N * N!). The space is O(N) for path, used and the recursion stack. The output is not counted.

For N = 10, there are 3,628,800 orderings. For N = 12, there are 479,001,600, which is too many to list. Check the limit on N before you choose this search.

60-Second Pitch

Common Questions

How is this different from Subsets (LC 78)?: Subsets builds each group in index order, so its loop starts at start and it saves at every node. Permutations restarts the loop at 0 in every call, uses used to avoid repeating an item, and saves only when path has all the items.
What are the time and space complexity?: O(N * N!) time, because there are N! leaves and each copy costs O(N). The space is O(N) for path, used and the recursion stack. The output is not counted.
What happens if the input has equal values?: Equal values count as different items, so the same ordering is saved several times. For [1, 1, 2], the search returns 6 orderings and only 3 are different. Permutations II (LC 47) sorts nums and skips i when i > 0, nums[i] == nums[i - 1] and used[i - 1] is False.
Could you swap items in place instead of using used?: Yes. You can swap nums[start] with nums[i], recurse on start + 1, and swap back. It uses no used array. The undo is still required, and with equal values the repeat check is harder, so the used version is easier to get right in an interview.
How do you cut the search when the problem has a rule?: Test the rule when you place an item, before backtrack() runs. In Beautiful Arrangement (LC 526), a number that breaks the rule at its position is not placed, so the whole branch below it is never built.

SWE Reasoning

Spot it

The statement asks for all arrangements, orderings or assignments, and the order of the answer matters.
Every item is used exactly once, so a full answer has length len(nums).
A rule can reject a placement early, for example a number must or must not stand at a given position, as in Beautiful Arrangement (LC 526).
The input is small, usually 8 to 10 items, because the answer has N! orderings.
You can say: for this position, which items are still free?

The invariant, step by step

backtrack() starts. If len(path) == len(nums), it saves list(path) and returns.
Otherwise the loop runs i from 0 to the end. If used[i] is True, then nums[i] is already in path, so continue skips it.
For a free i, the code sets used[i] = True and runs path.append(nums[i]). The invariant holds: used[i] is True exactly when nums[i] is in path.
backtrack() fills the remaining positions with the items that are still free.
path.pop() and used[i] = False restore both. path and used are now as they were before step 3, so the next i sees a correct state.
The picks form a choice for each position, so each full path is a different ordering and is saved once.

Traps

No used[i] = False after the call. The flag stays True after its branch returns, so every later branch skips that item. permute([1, 2]) returns [[1, 2]].
Saving at every node. A permutation needs all items. Saving at every call also saves [] and every shorter list. permute([1, 2]) returns [[], [1], [1, 2], [2], [2, 1]].
Saving path and not list(path). The code saves one list object and keeps changing it, so the saved lists are all empty at the end.
Checking the rule only on a full ordering. In Beautiful Arrangement (LC 526), the rule belongs to each position. Test it when you place the number, so a bad number cuts its whole branch. Testing at the end still builds all n! orderings.
A large N. N = 12 needs about 479 million orderings. Read the constraints first.

Practice

Theory Context•Backtracking & State Search

Builds on Subsets, which you haven’t finished yet.

P2MediumBuilt on Subsets~6 min speedrun

Built on

SubsetsA used array replaces start, so any element not yet in path can come next, and each element is used once.

Grows into

Constraint Backtracking

The problem

Permutations (LC 46)(opens leetcode.com)

Given an array nums of distinct integers, return every possible ordering of all its elements -- i.e., every permutation -- in any order.

A permutation uses each element from nums exactly once, arranged into some linear sequence.

Example 1

Input:nums = [1,2,3]

Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Three distinct numbers can be ordered in 3 * 2 * 1 = 6 ways.

Permutations

elements ➔ unused candidate selection ➔ boolean visited array

Spot it when: Order matters and every element is used exactly once: arrangements, orderings, assigning people to seats.

Permutations

Python

1	from typing import Callable, List, TypeVar
2
3	Item = TypeVar("Item")
4
5
6	def permutations(items: List[Item], can_place: Callable[[List[Item], Item], bool]) -> List[List[Item]]:
7	"""Permutations: every ordering of items, each position filled with an item that is not in path yet.
8	can_place(path, item) says whether item may come next after path. It prunes a branch early.
9	Precondition: equal items count as different items, so equal values give repeated orderings.
10	For equal values (Permutations II), sort the values and pass (value, index) pairs.
11	Then skip a pair when the equal pair just before it is not in path yet.
12	N = len(items). T = the cost of one can_place call.
13	Time: O(N * N! * T) \| Space: O(N) path + recursion stack, output not counted
14	"""
15	results: List[List[Item]] = []
16	path: List[Item] = []
17	used = [False] * len(items) # used[i] is true exactly when items[i] is in path
18
19	def backtrack() -> None:
20	# 1. Save a Full Ordering:
21	# path only counts as one ordering once it holds every item, so stop and save
22	# it there; a shorter path is still missing items and is not a real answer.
23	if len(path) == len(items):
24	results.append(list(path))
25	return
26
27	for i in range(len(items)):
28	# 2. Offer Every Unused Item:
29	# The loop restarts at 0 every call, so any item not already in path may
30	# come next; used[i] and can_place rule out the ones that cannot.
31	if used[i] or not can_place(path, items[i]):
32	continue
33
34	# 3. Choose, Explore, Un-choose:
35	# Mark items[i] used and append it, recurse so the next position sees it
36	# taken, then undo both marks so a later i in this loop can still use it.
37	used[i] = True
38	path.append(items[i])
39	backtrack()
40	path.pop()
41	used[i] = False
42
43	backtrack()
44	return results

Invariant: used[i] is true exactly when nums[i] is in path, so path never holds the same element twice.

See it run

Permutations, step by step

path []saved 0

The top row is nums. The middle row is used. The bottom row is path, filled from the left.

i the index the loop is looking at
used[i] the used flag that is read or set to True
path the slot just added to path
undo the slot or flag just reset by the undo

nums is [1, 2]. path is empty, and every used[i] is False.

nums

used

False

path

1 / 18

Gotchas1 of 4

The trap
Gotcha 1: Leaving out used[i] = False after the recursive call
Mistake
```
path.pop()
```
Fix
```
path.pop()
used[i] = False
```
What happens: used[i] becomes True when nums[i] is placed. Without the reset, it stays True after the branch returns. Every later branch then skips nums[i]. So only the first ordering is saved.
Example: nums = [1, 2]
Mistake: returns [[1, 2]]Fix: returns [[1, 2], [2, 1]]
Gotcha 2: Saving path before it holds every element
Mistake
```
results.append(list(path))
```
Fix
```
if len(path) == len(nums):
    results.append(list(path))
    return
```
What happens: Subsets (LC 78) saves path at every node. A permutation must use every element, so it is ready only when len(path) == len(nums). Saving at every node also saves the empty list and every shorter path.
Example: nums = [1, 2]
Mistake: returns [[], [1], [1, 2], [2], [2, 1]]Fix: returns [[1, 2], [2, 1]]
Gotcha 3: Using this search when n is larger than about 10
What happens: The search builds every ordering, and each full ordering costs O(n) to copy. So the time is O(n · n!). n = 10 gives 3,628,800 orderings. n = 12 gives 479,001,600 orderings, which is too many to list. Check the constraints before you choose this search.
Gotcha 4: Checking the rule only after the ordering is complete
Mistake
```
if len(path) == n and all(v % p == 0 or p % v == 0 for p, v in enumerate(path, 1)):
    count += 1
```
Fix
```
if not used[v] and (v % pos == 0 or pos % v == 0):
```
What happens: Beautiful Arrangement (LC 526) has a rule for each position. Checking it only on a full ordering builds all n! orderings first. The count is the same, but the search is much slower. Test the rule when you place each number v at position pos, counted from 1. A number that breaks the rule then cuts its whole branch at once.

Not this one if…

Order does not matter, as in Combinations (LC 77): [1, 2] and [2, 1] are the same answer, so listing every ordering returns duplicates. See Combinations

Deep Dive

What changes from Subsets: the loop restarts at 0

So the loop starts at 0 in every call, and a used array records which items are already in path. The loop skips i when used[i] is True.

A permutation must use every item. For this reason the code saves only when len(path) == len(nums). Saving at every node, as Subsets does, would also save the shorter lists.

Why each ordering appears exactly once

For nums = [1, 2, 3], the result has 6 orderings, and backtrack runs 16 times: 1 first call, 3 at depth 1, 6 at depth 2 and 6 at depth 3.

Why the undo has two lines

Take nums = [1, 2]. Choosing does two things: used[i] = True and path.append(nums[i]). So undoing must also do two things: path.pop() and used[i] = False.

The board shows both lines as two steps. The first pop returns path to [1], but used[1] is still True. Only the second line makes nums[1] available again.

Without used[i] = False, permute([1, 2]) returns [[1, 2]], not [[1, 2], [2, 1]]. After the first branch, used[0] and used[1] both stay True, so the second branch has nothing to place.

The cost, and repeated values

There are N! leaves, and saving each one copies path in O(N). The time is O(N * N!). The space is O(N) for path, used and the recursion stack. The output is not counted.

For N = 10, there are 3,628,800 orderings. For N = 12, there are 479,001,600, which is too many to list. Check the limit on N before you choose this search.

60-Second Pitch

Common Questions

How is this different from Subsets (LC 78)?: Subsets builds each group in index order, so its loop starts at start and it saves at every node. Permutations restarts the loop at 0 in every call, uses used to avoid repeating an item, and saves only when path has all the items.
What are the time and space complexity?: O(N * N!) time, because there are N! leaves and each copy costs O(N). The space is O(N) for path, used and the recursion stack. The output is not counted.
What happens if the input has equal values?: Equal values count as different items, so the same ordering is saved several times. For [1, 1, 2], the search returns 6 orderings and only 3 are different. Permutations II (LC 47) sorts nums and skips i when i > 0, nums[i] == nums[i - 1] and used[i - 1] is False.
Could you swap items in place instead of using used?: Yes. You can swap nums[start] with nums[i], recurse on start + 1, and swap back. It uses no used array. The undo is still required, and with equal values the repeat check is harder, so the used version is easier to get right in an interview.
How do you cut the search when the problem has a rule?: Test the rule when you place an item, before backtrack() runs. In Beautiful Arrangement (LC 526), a number that breaks the rule at its position is not placed, so the whole branch below it is never built.

SWE Reasoning

Spot it

The statement asks for all arrangements, orderings or assignments, and the order of the answer matters.
Every item is used exactly once, so a full answer has length len(nums).
A rule can reject a placement early, for example a number must or must not stand at a given position, as in Beautiful Arrangement (LC 526).
The input is small, usually 8 to 10 items, because the answer has N! orderings.
You can say: for this position, which items are still free?

The invariant, step by step

backtrack() starts. If len(path) == len(nums), it saves list(path) and returns.
Otherwise the loop runs i from 0 to the end. If used[i] is True, then nums[i] is already in path, so continue skips it.
For a free i, the code sets used[i] = True and runs path.append(nums[i]). The invariant holds: used[i] is True exactly when nums[i] is in path.
backtrack() fills the remaining positions with the items that are still free.
path.pop() and used[i] = False restore both. path and used are now as they were before step 3, so the next i sees a correct state.
The picks form a choice for each position, so each full path is a different ordering and is saved once.

Traps

No used[i] = False after the call. The flag stays True after its branch returns, so every later branch skips that item. permute([1, 2]) returns [[1, 2]].
Saving at every node. A permutation needs all items. Saving at every call also saves [] and every shorter list. permute([1, 2]) returns [[], [1], [1, 2], [2], [2, 1]].
Saving path and not list(path). The code saves one list object and keeps changing it, so the saved lists are all empty at the end.
Checking the rule only on a full ordering. In Beautiful Arrangement (LC 526), the rule belongs to each position. Test it when you place the number, so a bad number cuts its whole branch. Testing at the end still builds all n! orderings.
A large N. N = 12 needs about 479 million orderings. Read the constraints first.

Practice

Theory Context•Backtracking & State Search

Builds on Subsets, which you haven’t finished yet.

P2MediumBuilt on Subsets~6 min speedrun

Built on

SubsetsA used array replaces start, so any element not yet in path can come next, and each element is used once.

Grows into

Constraint Backtracking

The problem

Permutations (LC 46)(opens leetcode.com)

Given an array nums of distinct integers, return every possible ordering of all its elements -- i.e., every permutation -- in any order.

A permutation uses each element from nums exactly once, arranged into some linear sequence.

Example 1

Input:nums = [1,2,3]

Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Three distinct numbers can be ordered in 3 * 2 * 1 = 6 ways.

Permutations

elements ➔ unused candidate selection ➔ boolean visited array

Spot it when: Order matters and every element is used exactly once: arrangements, orderings, assigning people to seats.

Permutations

Python

1	from typing import Callable, List, TypeVar
2
3	Item = TypeVar("Item")
4
5
6	def permutations(items: List[Item], can_place: Callable[[List[Item], Item], bool]) -> List[List[Item]]:
7	"""Permutations: every ordering of items, each position filled with an item that is not in path yet.
8	can_place(path, item) says whether item may come next after path. It prunes a branch early.
9	Precondition: equal items count as different items, so equal values give repeated orderings.
10	For equal values (Permutations II), sort the values and pass (value, index) pairs.
11	Then skip a pair when the equal pair just before it is not in path yet.
12	N = len(items). T = the cost of one can_place call.
13	Time: O(N * N! * T) \| Space: O(N) path + recursion stack, output not counted
14	"""
15	results: List[List[Item]] = []
16	path: List[Item] = []
17	used = [False] * len(items) # used[i] is true exactly when items[i] is in path
18
19	def backtrack() -> None:
20	# 1. Save a Full Ordering:
21	# path only counts as one ordering once it holds every item, so stop and save
22	# it there; a shorter path is still missing items and is not a real answer.
23	if len(path) == len(items):
24	results.append(list(path))
25	return
26
27	for i in range(len(items)):
28	# 2. Offer Every Unused Item:
29	# The loop restarts at 0 every call, so any item not already in path may
30	# come next; used[i] and can_place rule out the ones that cannot.
31	if used[i] or not can_place(path, items[i]):
32	continue
33
34	# 3. Choose, Explore, Un-choose:
35	# Mark items[i] used and append it, recurse so the next position sees it
36	# taken, then undo both marks so a later i in this loop can still use it.
37	used[i] = True
38	path.append(items[i])
39	backtrack()
40	path.pop()
41	used[i] = False
42
43	backtrack()
44	return results

Invariant: used[i] is true exactly when nums[i] is in path, so path never holds the same element twice.

See it run

Permutations, step by step

path []saved 0

The top row is nums. The middle row is used. The bottom row is path, filled from the left.

i the index the loop is looking at
used[i] the used flag that is read or set to True
path the slot just added to path
undo the slot or flag just reset by the undo

nums is [1, 2]. path is empty, and every used[i] is False.

nums

used

False

path

1 / 18

Gotchas1 of 4

The trap
Gotcha 1: Leaving out used[i] = False after the recursive call
Mistake
```
path.pop()
```
Fix
```
path.pop()
used[i] = False
```
What happens: used[i] becomes True when nums[i] is placed. Without the reset, it stays True after the branch returns. Every later branch then skips nums[i]. So only the first ordering is saved.
Example: nums = [1, 2]
Mistake: returns [[1, 2]]Fix: returns [[1, 2], [2, 1]]
Gotcha 2: Saving path before it holds every element
Mistake
```
results.append(list(path))
```
Fix
```
if len(path) == len(nums):
    results.append(list(path))
    return
```
What happens: Subsets (LC 78) saves path at every node. A permutation must use every element, so it is ready only when len(path) == len(nums). Saving at every node also saves the empty list and every shorter path.
Example: nums = [1, 2]
Mistake: returns [[], [1], [1, 2], [2], [2, 1]]Fix: returns [[1, 2], [2, 1]]
Gotcha 3: Using this search when n is larger than about 10
What happens: The search builds every ordering, and each full ordering costs O(n) to copy. So the time is O(n · n!). n = 10 gives 3,628,800 orderings. n = 12 gives 479,001,600 orderings, which is too many to list. Check the constraints before you choose this search.
Gotcha 4: Checking the rule only after the ordering is complete
Mistake
```
if len(path) == n and all(v % p == 0 or p % v == 0 for p, v in enumerate(path, 1)):
    count += 1
```
Fix
```
if not used[v] and (v % pos == 0 or pos % v == 0):
```
What happens: Beautiful Arrangement (LC 526) has a rule for each position. Checking it only on a full ordering builds all n! orderings first. The count is the same, but the search is much slower. Test the rule when you place each number v at position pos, counted from 1. A number that breaks the rule then cuts its whole branch at once.

Not this one if…

Order does not matter, as in Combinations (LC 77): [1, 2] and [2, 1] are the same answer, so listing every ordering returns duplicates. See Combinations

Deep Dive

What changes from Subsets: the loop restarts at 0

So the loop starts at 0 in every call, and a used array records which items are already in path. The loop skips i when used[i] is True.

A permutation must use every item. For this reason the code saves only when len(path) == len(nums). Saving at every node, as Subsets does, would also save the shorter lists.

Why each ordering appears exactly once

For nums = [1, 2, 3], the result has 6 orderings, and backtrack runs 16 times: 1 first call, 3 at depth 1, 6 at depth 2 and 6 at depth 3.

Why the undo has two lines

Take nums = [1, 2]. Choosing does two things: used[i] = True and path.append(nums[i]). So undoing must also do two things: path.pop() and used[i] = False.

The board shows both lines as two steps. The first pop returns path to [1], but used[1] is still True. Only the second line makes nums[1] available again.

Without used[i] = False, permute([1, 2]) returns [[1, 2]], not [[1, 2], [2, 1]]. After the first branch, used[0] and used[1] both stay True, so the second branch has nothing to place.

The cost, and repeated values

There are N! leaves, and saving each one copies path in O(N). The time is O(N * N!). The space is O(N) for path, used and the recursion stack. The output is not counted.

For N = 10, there are 3,628,800 orderings. For N = 12, there are 479,001,600, which is too many to list. Check the limit on N before you choose this search.

60-Second Pitch

Common Questions

How is this different from Subsets (LC 78)?: Subsets builds each group in index order, so its loop starts at start and it saves at every node. Permutations restarts the loop at 0 in every call, uses used to avoid repeating an item, and saves only when path has all the items.
What are the time and space complexity?: O(N * N!) time, because there are N! leaves and each copy costs O(N). The space is O(N) for path, used and the recursion stack. The output is not counted.
What happens if the input has equal values?: Equal values count as different items, so the same ordering is saved several times. For [1, 1, 2], the search returns 6 orderings and only 3 are different. Permutations II (LC 47) sorts nums and skips i when i > 0, nums[i] == nums[i - 1] and used[i - 1] is False.
Could you swap items in place instead of using used?: Yes. You can swap nums[start] with nums[i], recurse on start + 1, and swap back. It uses no used array. The undo is still required, and with equal values the repeat check is harder, so the used version is easier to get right in an interview.
How do you cut the search when the problem has a rule?: Test the rule when you place an item, before backtrack() runs. In Beautiful Arrangement (LC 526), a number that breaks the rule at its position is not placed, so the whole branch below it is never built.

SWE Reasoning

Spot it

The statement asks for all arrangements, orderings or assignments, and the order of the answer matters.
Every item is used exactly once, so a full answer has length len(nums).
A rule can reject a placement early, for example a number must or must not stand at a given position, as in Beautiful Arrangement (LC 526).
The input is small, usually 8 to 10 items, because the answer has N! orderings.
You can say: for this position, which items are still free?

The invariant, step by step

backtrack() starts. If len(path) == len(nums), it saves list(path) and returns.
Otherwise the loop runs i from 0 to the end. If used[i] is True, then nums[i] is already in path, so continue skips it.
For a free i, the code sets used[i] = True and runs path.append(nums[i]). The invariant holds: used[i] is True exactly when nums[i] is in path.
backtrack() fills the remaining positions with the items that are still free.
path.pop() and used[i] = False restore both. path and used are now as they were before step 3, so the next i sees a correct state.
The picks form a choice for each position, so each full path is a different ordering and is saved once.

Traps

No used[i] = False after the call. The flag stays True after its branch returns, so every later branch skips that item. permute([1, 2]) returns [[1, 2]].
Saving at every node. A permutation needs all items. Saving at every call also saves [] and every shorter list. permute([1, 2]) returns [[], [1], [1, 2], [2], [2, 1]].
Saving path and not list(path). The code saves one list object and keeps changing it, so the saved lists are all empty at the end.
Checking the rule only on a full ordering. In Beautiful Arrangement (LC 526), the rule belongs to each position. Test it when you place the number, so a bad number cuts its whole branch. Testing at the end still builds all n! orderings.
A large N. N = 12 needs about 479 million orderings. Read the constraints first.