Backtracking

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

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

सभी क्रमचय

path वर्तमान आंशिक व्यवस्था है; जोड़ें, recurse करें, pop करें।

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 ही पूरा खेल है।