# Backtracking — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/backtracking

> Build a candidate step by step; abandon it the moment it can't work.

## Choose, explore, un-choose

At each step: make a choice, recurse, then **undo the choice** before trying the next. Prune branches that already violate a constraint. It's DFS over the tree of partial solutions.

## All permutations

`path` is the current partial arrangement; add, recurse, pop.

```python
def permutations(nums):
    res, path, used = [], [], [False] * len(nums)
    def bt():
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i, n in enumerate(nums):
            if used[i]:
                continue
            used[i] = True; path.append(n)
            bt()
            used[i] = False; path.pop()   # un-choose
    bt()
    return res
```

## Classic problems

Subsets, combinations, permutations, N-Queens, Sudoku, word search, generating valid parentheses. Cost is often exponential — good pruning is the whole game.