# Recursion Backtracking

> Generate all valid arrangements using backtracking with pruning. Use when solving permutations, combinations, subsets, N-queens, sudoku, or constraint satisfaction problems.

- Skill: `knoopx/recursion-backtracking` (Agent Skill)
- Install (CLI): `npx skillmds@latest add knoopx/recursion-backtracking`
- Raw SKILL.md: https://api.skillmd.com/api/skills/knoopx/recursion-backtracking/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: AI & ML
- Author: knoopx (https://skillmd.com/u/knoopx)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/knoopx/recursion-backtracking

---


## When to use

Use backtracking for constraint satisfaction and combinatorial generation: permutations, combinations, subsets, N-queens, sudoku, valid arrangements.

## Rules

- Pattern: make a choice, recurse, undo the choice (backtrack)
- Prune early — skip branches that already violate constraints to avoid exploring dead ends
- For subsets: at each element, choose to include or exclude it (2^n total)
- For permutations: choose each unused element at each position (n! total)
- ALWAYS pass state by reference and undo mutations rather than copying
- NEVER copy state — it's wasteful and slow
- If the problem says "generate all" or "find all valid," backtracking is usually the right approach

## Complexity

Subsets: 2^n. Permutations: n!.

## Example

Subsets of [1,2,3]: at each element, branch include/exclude. `def solve(i): if i==n: yield list(path); return; path.append(nums[i]); solve(i+1); path.pop(); solve(i+1)`.