leetcode/template/algo_recursive_backtrack.py at master · catinthecode/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
"""
recursive function template
"""

def myfunc(n, **kwargs):
    # base case
    if n == 0:
        return
    # recursive call to myself
    else:
        myfunc(n-1)

"""
backtrack template
"""
def backtrack(choices, chosen):
    # base case
    if not choices:
        print(chosen)
        return

    # recursive case
    # choose current element choices[0]
    chosen.append(choices[0])
    # explore
    backtrack(choices[1:], chosen)
    # unchoose current element choices[0]
    chosen.pop()

"""
Knapsack problem / backtrack
"""
def fill_knapsack(objects, weight, best_score):
    if weight < 0: # too many objects
        return 0
    local_best_score = best_score
    for i, obj in enumerate(objects):
        curr_value = best_score + obj.value
        curr_weight = weight + obj.weight

        # remove current obj

        # recursive exploration with current obj removed
        curr_value = fill_knapsack(objects[:i]+objects[i+1:], curr_weight, curr_value)
        if local_best_score < curr_value:
            local_best_score = curr_value
        # restore current obj

    return local_best_score

"""
walk maze

start marked with 'S', finish marked with 'F', wall marked with 'X'

approach:
1. mark position seen with period '.', mark backtracking with 'b'
2. have a case for all valid inputs
3. must have base cases
4. make forward progress toward the base case
"""
def solve_maze(row, col, grid):
    # base case
    # if wall
    if (grid[row][col] == 'X'):
        return False
    # if visited
    if (grid[row][col] == '.'):
        return False
    # if finish
    if (grid[row][col] == '.'):
        return True

    # mark visited
    grid[row][col] == '.'

    # recusrively call solve_maze(row, col, grid) for all directions,
    # if any direction returns True, we return True
    if solve_maze(row-1, col, grid):
        return True

    if solve_maze(row, col+1, grid):
        return True

    if solve_maze(row+1, col, grid):
        return True

    if solve_maze(row, col-1, grid):
        return True

    # no direction is successful
    # mark as backtrack
    grid[row][col] == 'b'
    return False

"""
Classic exhaustive permutation pattern

pseudo code:
    If you have no more characters left to rearrange, print current permutation
    for (every possible choice among the characters left to rearrange):
        Make a choice and add that character to the permutation so far
        Use recursion to rearrange the remaining letters
"""
def recursive_permute(sofar, rest):
    if not rest:
        print(sofar)
    else:
        for i in range(len(rest)):
            recursive_permute(sofar + rest[i], rest[:i]+rest[i+1:])


"""
Classic exhaustive subset pattern

    If there are no more elements remaining,
        print current subset
    else
        Consider the next element of those remaining
        Try adding it to the current subset, and use recursion to build subsets from here
        Try not adding it to current subset, and use recursion to build subsets from here

"""
def recursive_subsets(sofar, rest):
    if not rest:
        print(sofar)
    else:
        # include first char
        recursive_subsets(sofar + rest[0], rest[1:])
        # exclude first char
        recursive_subsets(sofar, rest[1:])