回溯采用试错的方法解决问题。一旦发现当前步骤失败，回溯方法就返回上一个步骤，选择另一种方案继续试错。

排列

给定一组列表数据，输出所有的可能排列 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def solvePermutation(self, array):
        self.helper(array, [])

    def helper(self, array, solution):
        if len(array) == 0:
            print(solution)
            return
        for i in range(len(array)):
            new_solution = solution + [array[i]]        # 新建排序列表
            new_array = array[:i] + array[i+1:]         # 新建待选择列表
            self.helper(new_array, new_solution)        # 回溯


if __name__ == '__main__':
    # 选输出下面的元素的几种排列形式: ['红', '橙', '黄', '绿']
    Solution().solvePermutation(['红', '橙', '黄', '绿']

组合

给定一组列表数据，输出所有的可能组合形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def solveCombination(self, array, n):
        self.helper(array, [], n)

    def helper(self, array, solution, n):
        if len(solution) == n:
            print(solution)
            return
        for i in range(len(array)):
            new_solution = solution + [array[i]]        # 新建组合列表
            new_array = array[i+1:]                     # 新建待选择列表表
            self.helper(new_array, new_solution, n)     # 回溯


if __name__ == '__main__':
    # 选输出下面的元素的几种组合形式: ['A', 'B', 'C', 'D', 'E', 'F']
    Solution().solveCombination(['A', 'B', 'C', 'D', 'E', 'F'], 3)

单词查找

还记得报纸上那种找单词的游戏吗？就是那种在一堆横向或竖向找出单词的游戏。
如下所示游戏盘面中能找出来四个单词(world,week,rose,reef)，给出一个单词通过回溯法得出这个单词是否存在于盘面中。
如，给予”world”返回True，给予”hello”返回False，
a, c, r, y, l
l, w, o, r, i
a, f, d, l, e
k, e, e, w, e
o, d, r, o, s

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
class Soultion:
    def helper(self, board, current, row, column):
        if len(current) == 0:  # 如果找到单词返回True
            return True

        if 0 <= row < len(board) and 0 <= column < len(board[0]):
            if board[row][column] == current[0]:
                board[row][column] = ""  # 找到字母时应临时从盘面中删除
                if self.helper(board, current[1:], row - 1, column):  # 检查上
                    return True
                if self.helper(board, current[1:], row + 1, column):  # 检查下
                    return True
                if self.helper(board, current[1:], row, column - 1):  # 检查左
                    return True
                if self.helper(board, current[1:], row, column + 1):  # 检查右
                    return True
                board[row][column] = current[0]  # 如果上下左右都没有剩余字母，返回False
        return False

    def wordSearch(self, board, word):
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.helper(board, word, i, j):
                    return True
        return False


if __name__ == '__main__':
    board = [['a', 'c', 'r', 'y', 'l'], ['l', 'w', 'o', 'r', 'i'], ['a', 'f', 'd', 'l', 'e'],
             ['k', 'e', 'e', 'w', 'e'], ['o', 'd', 'r', 'o', 's']]
    print(Soultion().wordSearch(board, "world"))