刷题记录 | 回溯算法题

电话号码的组合

题目：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

示例：

输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

解题思路：

回溯法。即先选择一条路走到黑，走不动了退回来一步，再探索其他的方向，该位置的方向探索完之后，再退出来一步，继续探索。

回归到这道题就是：假设该字符串为 ‘23’，选择第一个数字 2，接下来需要遍历 2 代表的字母 ‘a’, ‘b’, ‘c’。首先选择字母 ‘a’，然后到数字 3 对应的字母，‘d’, ‘e’, ‘f’，所有的字母组合完后，退出到 ‘b’，再重复。直到遍历完 2 代表的字母。

Python 代码如下所示：

def letterCombinations(self, digits: str) -> List[str]: # 回溯方法 if not digits: return [] phoneMap = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz", } def backtrack(index): if index == len(digits): bigList.append("".join(smallList)) else: numb = digits[index] for letter in phoneMap[numb]: smallList.append(letter) backtrack(index+1) smallList.pop() bigList = list() smallList = list() backtrack(0) return bigList

括号生成

题目：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例：

输入：n = 3 输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

解析：

在任意一个位置，左括号的数量大于等于右括号的数量。 生成的括号对数中，左括号的数量等于右括号的数量。

用回溯法，即深度优先搜索，代码如下：

def generatePare(n): res = [] dfs(res, n, n, '') return res def dfs(res, left, right, path): if left == 0 and right == 0: res.append(path) if left > 0: dfs(res, left-1, right, path+'(') if left < right: dfs(res, left, right-1, path+')')

无重复字符串的排列组合

示例：

输入：S = "qwe" 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

Python代码如下：

def permutation(S): if len(S) == 0: return [] res = [] def backtrack(S, path, res): if S == '': res.append(path) return for i in range(len(S)): cur = S[i] backtrack(S[:i]+S[i+1:], path+cur, res) backtrack(S, '', res) return res

全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

Python 实现：

def permutation(nums): def dfs(nums, size, depth, path, used, res): if depth == size: res.append(path[:]) for i in range(size): if not used[i]: used[i] = True path.append(used[i]) dfs(nums, size, depth+1, path, used, res) used[i] = False path.pop() size = len(nums) res = [] if len(nums) == 0: return [] used = [False for _ in range(size)] dfs(nums, size, 0, [], used, res) return res

全排列②

示例：

输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]

看示例我们可以很清楚地发现区别，即存在重复项。那和上一道题相比，多个剪枝的操作。 首先将数组排序，然后将相同的元素剪枝。 代码如下：

def permutation_2(nums): def dfs(nums, size, depth, path, used, res): if size == depth: res.append(path.copy()) return for i in range(size): if not used[i]: if i > 0 and nums[i] == nums[i-1] and not nums[i]: continue nums[i] = True dfs(nums, size, depth+1, path, used, res) used[i] = False path.pop() size = len(nums) if len(nums) == 0: return [] res = [] sorted(nums) used = [False for _ in range(size)] dfs(nums, size, 0, [], used, res) return res

另外通过小例子，来看一下 Python 当中，两种排序的区别：$sorted()$ 函数对数组本身的顺序不产生影响，要想彻底改变nums 的元素顺序，需要采用 $nums.sort()$ 函数。

nums = [1,1,4, 3, 2, 2, 1] sorted(nums) Out[20]: [1, 1, 1, 2, 2, 3, 4] nums Out[21]: [1, 1, 4, 3, 2, 2, 1] nums.sort() nums Out[23]: [1, 1, 1, 2, 2, 3, 4]

生成数组的两种方式：

[False for _ in range(5)] Out[24]: [False, False, False, False, False] [False] * 5 Out[25]: [False, False, False, False, False]