# Backtracking — डेटा स्ट्रक्चर और एल्गोरिदम

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

> उम्मीदवार को चरण दर चरण बनाएँ; जैसे ही यह काम न कर सके, छोड़ दें।

## चुनें, खोजें, अ-चुनें

हर चरण पर: एक चुनाव करें, recurse करें, फिर अगला आज़माने से पहले **चुनाव पूर्ववत करें**। उन शाखाओं को काटें जो पहले से बाधा तोड़ती हैं। यह आंशिक हलों के tree पर DFS है।

## सभी क्रमचय

`path` वर्तमान आंशिक व्यवस्था है; जोड़ें, 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
```

## क्लासिक समस्याएँ

Subsets, combinations, permutations, N-Queens, Sudoku, word search, वैध parentheses बनाना। लागत अक्सर घातांकी — अच्छी pruning ही पूरा खेल है।