Leetcode题之回溯法

发表于 | 分类于

前言-关于回溯法

什么是回溯法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。但是同时回溯法也容易遇到递归次数过多的问题影响时间复杂度，这时候就要开始考虑进行减支或者尝试DP算法。

基本思想

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

一般步骤

（1）针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
（2）确定结点的扩展搜索规则。
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

算法框架

  1. 问题框架

设问题的解是一个n维向量 \((a_1,a_2,………,a_n)\)，约束条件是 \(a_i(i=1,2,3,…..,n)\) 之间满足某种条件，记为\(f(a_i)\)。

  1. 非递归回溯框架

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    int a[n],i;
    初始化数组a[];
    i = 1;
    while (i>0(有路可走)   and  (未达到目标)){  // 还未回溯到头
        if(i > n){    // 搜索到叶结点
            搜索到一个解，输出；
        }else{ // 处理第i个元素
            a[i]第一个可能的值；
            while(a[i]在不满足约束条件且在搜索空间内){
                a[i]下一个可能的值；
            }
            if(a[i]在搜索空间内){
                标识占用的资源；
                i = i+1;  // 扩展下一个结点
            }else{
                清理所占的状态空间； // 回溯
                i = i – 1;
            }
        }
    }

  2. 递归回溯框架

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int a[n];
    try(int i){
        if(i>n)
            输出结果;
        else{
            for(j = 下界; j <= 上界; j=j+1){  // 枚举i所有可能的路径
                if(fun(j)){                 // 满足限界函数和约束条件
                    a[i] = j;
                    ...                         // 其他操作
                    try(i+1);
                    回溯前的清理工作（如a[i]置空值等）;
                }
            }
        }
    }

Leetcode 17. Letter Combinations of a Phone Number

题目描述 for 17

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

phone number

phone number

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

解题思路-遍历

遍历每一个数字代表的不同字母，找出所有组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        d = {'2':['a','b','c'],
            '3':['d','e','f'],
            '4':['g','h','i'],
            '5':['j','k','l'],
            '6':['m','n','o'],
            '7':['p','q','r','s'],
            '8':['t','u','v'],
            '9':['w','x','y','z']}
        result = d[digits[0]]
        for s in digits[1:]:
            al = d[s]
            temp = []
            for r in result:
                for a in al:
                    temp.append(r+a)
            result = temp
        return result

Leetcode 22. Generate Parentheses

问题描述 for 22

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

解题思路-BT

递归的找到所有合理解，通过一个变量 state 验证当前序列是否合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        self.gen(result, n, "", 0)
        return result

    def gen(self, res, n, s, state):
        if len(s) == 2*n:
            if state == 0:
                res.append(s)
            return
        # 如果 state 小于0则代表当前右括号比左括号多
        if state < 0:
            return
        self.gen(res, n, s+"(", state+1)
        self.gen(res, n, s+")", state-1)

Leetcode 46. Permutations

题目描述 for 46

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

解题思路-递归

通过递归的方式遍历所有可能的结果。对每个不在 temp 中的元素，现考虑它在此位置的情况，再pop，考虑其他元素在此处的地方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return None
        result = []
        self.trace(result, [], nums)
        return result

    def trace(self, result, temp, nums):
        if len(temp) == len(nums):
            result.append(temp.copy())
        else:
            for i in range(len(nums)):
                if nums[i] not in temp:
                    temp.append(nums[i])
                    self.trace(result, temp, nums)
                    temp.pop(-1)

Leetcode 78. Subsets

题目描述 for 78

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

解题思路-还是递归

使用递归的方式，对每种组合进行考虑。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def trace(result, temp, nums, i):
            result.append(temp)
            for i in range(i, len(nums)):
                trace(result, temp+[nums[i]], nums, i+1)

        if not nums:
            return []
        result = []
        trace(result, [], nums, 0)
        return result

问题描述 for 79

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

解题思路-从每个点进行递归

从每个点开始递归遍历，如果找到正确答案则返回，否则继续。

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
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def find(board, x, y, word, i):
            # x, y 代表当前所在单元，i表示已经找到的字长
            if i == len(word):
                return True
            # 越界检查，以及当前单元代表字符跟word里相应位置的是否一致
            if x < 0 or y < 0 or x == len(board) or y == len(board[0]) or board[x][y] != word[i]:
                return False
            # 对目前所在的单元进行已读标记
            tmp = board[x][y]
            board[x][y] = "#"
            # 单元格的四个方向查找
            exists = find(board, x+1, y, word, i+1) \
                or find(board, x, y+1, word, i+1) \
                or find(board, x-1, y, word, i+1) \
                or find(board, x, y-1, word, i+1)
            # 恢复board的已读标记
            board[x][y] = tmp
            return exists

        if not board:
            return False
        h = len(board)
        w = len(board[0])
        for i in range(len(board)):
            for j in range(len(board[0])):
                if find(board, i, j, word, 0):
                    return True
        return False

参考