Backtracking

Systematic search with pruning

Backtracking builds candidates step by step: choose an option, explore recursively, then unchoose (undo) it. It generates subsets (2ⁿ), permutations (n!) and combinations, and solves constraint problems such as N-Queens and Sudoku. Pruning (stopping when the remaining target is negative or a constraint is broken) keeps it practical. Copy the path when recording a result, because it keeps changing.

Subsets, permutations and combination sum, run

I ran this with Python 3.12.3 (standard library only). Three elements give 8 subsets; four give 24 permutations (the first three of [1, 2, 3] are shown); target 7 can be made as 2+2+3 or 7.

# Backtracking: subsets, permutations and combination sum
def subsets(nums):
    out, path = [], []
    def go(i):
        if i == len(nums):
            out.append(path[:]); return
        path.append(nums[i]); go(i + 1); path.pop()   # take
        go(i + 1)                                     # skip
    go(0)
    return out

def permutations(nums):
    out, path, used = [], [], [False] * len(nums)
    def go():
        if len(path) == len(nums):
            out.append(path[:]); return
        for i, x in enumerate(nums):
            if not used[i]:
                used[i] = True; path.append(x)
                go()
                path.pop(); used[i] = False
    go()
    return out

def combination_sum(cands, target):
    out, path = [], []
    def go(start, remaining):
        if remaining == 0:
            out.append(path[:]); return
        for i in range(start, len(cands)):
            if cands[i] <= remaining:                 # prune
                path.append(cands[i]); go(i, remaining - cands[i]); path.pop()
    go(0, target)
    return out

print(subsets([1, 2, 3]))
print(len(permutations([1, 2, 3, 4])), permutations([1, 2, 3])[:3])
print(combination_sum([2, 3, 6, 7], 7))

Output:

[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
24 [[1, 2, 3], [1, 3, 2], [2, 1, 3]]
[[2, 2, 3], [7]]

Append path[:], not path

Appending the list object itself records a reference that is later emptied by the undo steps.

त्वरित जाँच: What is the "unchoose" step in backtracking?

• Sorting the results
• Deleting the input
• Undoing the last choice after exploring it
• Returning early always