Backtracking

Contents

Backtracking#

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems which incrementally builds candidates to the solution and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot lead to a valid solution.

It is due to this backtracking behaviour, the backtracking algorithms are often much faster than the brute-force search algorithm, since it eliminates many unnecessary exploration.

def backtrack(candidate):
    if find_solution(candidate):
        output(candidate)
        return
    
    # iterate all possible candidates.
    for next_candidate in list_of_candidates:
        if is_valid(next_candidate):
            # try this partial candidate solution
            place(next_candidate)
            # given the candidate, explore further.
            backtrack(next_candidate)
            # backtrack
            remove(next_candidate)

Overall, the enumeration of candidates is done in two levels:

  • at the first level, the function is implemented as recursion. At each occurrence of recursion, the function is one step further to the final solution.

  • as the second level, within the recursion, we have an iteration that allows us to explore all the candidates that are of the same progress to the final solution.

Code Examples#

See here.

Here we have to explore all combinations of numbers from 1 to n of length k. Indeed, we could solve the problem with the paradigm of backtracking.

Problem - combinations Decision space- numbers from 1 to n without repetation Output- all combinatins of numbers from 1 to n of size k

def combine(n, k):   
    sol=[]
    def backtrack(k,comb,nex):
        # solution found
        if k==0:
            sol.append(comb.copy())
        else:
            # iterate through all possible candidates
            for i in range(nex,n+1):
                # add candidate
                comb.append(i)
                #backtrack
                backtrack(k-1,comb,i+1)
                # remove candidate
                comb.pop()
        
    backtrack(k,[],1)
    return sol

# test 
n = 4 
k = 2
print(combine(n, k))

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Contents