9. Backtracking

Backtracking

Nearly impossible to do Big O notation!

Backtracking deals with traversing a hierarchical tree from left to right, while moving back and forth between the left and right levels

A common examlpe is a Trie where we have some suffix abc and we want traverse all other combinations moving back and forth such as going to abcd and realizing we don't want that, we want abce

Pseudocode:

def problem(self, arr) -> List[str]:
    if check_edge_case_initially():
        return([])
    
    resp = []
    seen = set() #sometimes this is not needed, it depends on problem

    def backtrack(idx, path):
        if condition(path) and path not in seen:
            resp.append(path)
            seen.add(path)
            return
        
        for i in arr[idx]:
            path.append(i)
            backtrack(idx + 1, path)
            path.pop()
    
    backtrack(0, []) # set things in motion
    return(resp)

So as you can see above we will recursively go through until some condition(path) is met, and then that would return on callstack and we'd immediately get to path.pop() which would allow us to test the next test case

A good example is permutations of a list [1, 3, 5, 7] of length 3 We'd have callstack of:

backtrack(0, []) -> backtrack(1, [1]) -> backtrack(2, [1, 3]) -> backtrack(3, [1, 3, 5])

at this point we'd reach the condition(path), add `135` to resp, and pop off

Then we'd get to backtrack(3, [1, 3, 7]) becuase we are in a loop of for i in arr[idx]

Lastly that'd pop off, it would return, and we'd get into backtrack(2, [1, 5]) -> backtrack(3, [1, 5, 7])

Indexes

Using indexes is an easy way to loop through all permutations of some size $k$

A good example where this fails is Maximum Score Subsequence Size K where we go through all ${n \choose k} = {{n!} \over {k!} \cdot {(n-k)!}}$ possibilities and get a TLE exception

def problem(self, arr: List[int], size: int):
    prep()
    resp = []

    def backtrack(curr, start):
        if len(curr) == size and tuple(curr) not in seen:
            resp.append(curr[:]) # copy of curr
            return
            
        for i in range(start, len(arr)):
            curr += [i]
            backtrack(curr, i + 1)
            curr.pop()
        
        return
    
    backtrack([], 0)
    return(resp)

OR - like the pros do, just use itertools

def problem(self, arr: List[int], size: int):
    prep()
    resp = []

    # list of every combination
    combos = list(itertools.combinations(range(len(arr)), size))
    # list of every permutation
    permus = list(itertools.permutations(range(len(arr)), size))    
    return(resp)

Which utilizes the other_idx and popping to recursively go through every possible permutation

Permutations vs Combinations

Trie