Backtracking and constraint search · HTML
dfs(pos) chooses any unused index i, marks it, recurses to pos+1, then undoes. After sorting, skip nums[i]==nums[i-1] when the previous equal index is not used on the current path.
Recognition signals
- All permutations or fixed-length ordered arrangements must be output.
- One indexed element cannot be reused within an arrangement.
- Different choice orders are distinct outcomes.
- Every position selects from all remaining elements.
- Input may contain duplicates but output must be unique.
False friends
| Signal | Why it is different |
|---|
| Order-insensitive selection | Use start-based combination search; permutations create k! equivalent orders. |
| Only the number of permutations | A factorial or multiset formula, or DP, avoids generation. |
| Only the best arrangement is wanted | Greedy, DP, or assignment structure may optimize without enumerating every order. |
Core invariant
At depth pos, path contains exactly pos distinct indices, used matches path exactly, and equal values at one level expand through only their canonical representative.
State, transition, and processing order
| Item | Definition |
|---|
| State | Current position, path, and used booleans; alternatively, an in-place array whose prefix [0,pos) is fixed. |
| Transition | Choose an unused index, mark and append it, recurse, then remove and unmark in reverse order. |
| Frontier / order | Each tree level represents one output position, with branching decreasing as elements are consumed. |
Python skeleton
def unique_permutations(nums):
nums = sorted(nums)
used = [False] * len(nums)
path, out = [], []
def dfs():
if len(path) == len(nums):
out.append(path.copy())
return
for i, value in enumerate(nums):
if used[i]: continue
if i and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True; path.append(value)
dfs()
path.pop(); used[i] = False
dfs()
return out
Correctness sketch
- used makes every root-to-leaf path consume each index exactly once, so every leaf is a legal permutation.
- For distinct values, every remaining value is available at every position, making every permutation reachable.
- Among equal values, the first unused representative is forced at each level; this removes only swaps of indistinguishable values, not distinct value sequences.
Complexity
| Time | Space | Parameters |
|---|
| Θ(n·n!) without duplicates, dominated by output copies | O(n) stack/path/used excluding output | n is item count; duplicate counts c_i reduce outputs to n!/∏c_i!. |
Edge cases
- whether empty input emits one empty permutation
- duplicate values
- object sorting/equality rules
- partial-length permutations
- copying output
- factorial explosion
Error patterns
| Pattern | Why it fails / fix |
|---|
| Using start instead of used | start enforces increasing indices and generates combinations, not permutations. |
| Reversing the duplicate-skip condition | Skip when the previous equal value is not used, which identifies a same-level duplicate. |
| Failing to unmark used | Later sibling branches permanently lose a candidate. |
| Generating all then deduplicating with a set | This explores redundant factorial branches and consumes excess memory; prune at the tree level. |
Selection and exclusion rules
- First decide whether order distinguishes outcomes.
- Sort duplicate inputs and prune equal same-level choices.
- Confirm that every permutation truly must be materialized.
- For only an optimum arrangement, seek a specialized optimization model.
Original micro-example
| Part | Detail |
|---|
| Result | AAB, ABA, and BAA appear exactly once. |
| Setup | Find unique arrangements of badges [A,A,B]. |
| Trace | At the root, the second A is skipped while the first A is unused; deeper down it becomes legal after the first A is selected. |
Recall prompts
My notes