[leetcode] [Tag Backtracking回溯]
回溯法
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
解题一般步骤：
（1）针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
（2）确定结点的扩展搜索规则
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
17. Letter Combinations of a Phone Number(Medium)
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.
Example:
给定一串2-9的数字，返回其在手机按钮上可能的组合。
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
image.png
思路：经典的回溯组合问题，可以先把数字对应的字母序列做一个mapping字典，循环或递归加入每个字符，需要一个list保存当前正在加入的字符串。
循环的方法
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits:
return []
mapping = {
'2':'abc',
'3':'def',
'4':'ghi',
'5':'jkl',
'6':'mno',
'7':'pqrs',
'8':'tuv',
'9':'wxyz'
}
result = [""]
for d in digits:
tmp = []
for letter in mapping[d]:
for res in result:
tmp.append(res + letter)
result = tmp
return result
递归的方法
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits:
return []
d = {'2':"abc",
'3':"def",
'4':"ghi",
'5':"jkl",
'6':"mno",
'7':"pqrs",
'8':"tuv",
'9':"wxyz"
}
res = []
self.dfs(d, digits, "", res)
return res
def dfs(self, d, digits, tmp , res):
if not digits:
res.append(tmp)
else:
for num in d[digits[0]]:
self.dfs(d, digits[1:], tmp + num, res)
22. Generate Parentheses(Medium)
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
给的那个n对括号，写出所有配对括号的组合
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
思路：dfs回溯，设left，right来表示剩余括号数，每当出现一个括号就让left或right减一。
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
if n < 1:
return [""]
res = []
self.dfs(n ,n , res, "")
return res
def dfs(self, left, right, res, tmp):
if left > right or left < 0 or right < 0:
return
if left == 0 and right == 0:
res.append(tmp)
self.dfs(left - 1, right, res, tmp + '(')
self.dfs(left , right - 1, res, tmp + ')')
39. Combination Sum(Medium)
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
给定一些被选中的数字（没有重复的）和一个目标数，找到满足在给定数字序列中和为目标数的集合。数字可以重复使用
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
所有的数都是正整数，不能包含重复的组合。
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
思路：该题数组没有排好序，首先得排序。剩下的同样，dfs递归的套路都差不多，用一个辅助函数，每遍历一个数就加入待定的数组tmp，再把目标书target 减去当前遍历过的数。
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
candidates.sort()
self.dfs(candidates, 0, target, res, [])
return res
def dfs(self, candidates, index, target, res, tmp):
if target < 0:
return
if target == 0:
res.append(tmp)
return
for i in range(index, len(candidates)):
self.dfs(candidates, i, target - candidates[i] , res, tmp+[candidates[i]])
40. Combination Sum II(Medium)
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
给定一些被选中的数字和一个目标数，找到满足在给定数字序列中和为目标数的集合。每个数只能使用一次
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
思路：跟39题非常像，区别在于数组内的数不能重复使用，但数组内可以有重复的数，注意一下相同的数不要遍历两次产生重合的结果就好了
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
if not candidates:
return []
candidates.sort()
res = []
self.dfs(candidates, target, res, [])
return res
def dfs(self, candidates, target, res ,tmp):
if target < 0:
return
if target == 0:
res.append(tmp)
return
for i in range(len(candidates)):
if i!=0 and candidates[i] == candidates[i-1]:
continue
self.dfs(candidates[i+1:], target-candidates[i], res, tmp+[candidates[i]])
46. Permutations(Medium)
Given a collection of distinct integers, return all possible permutations.
给定不同的整数的集合,返回所有可能的排列。
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
思路：O(n2)的方法，如果上面的题会了这道题就算简单题了，47题、77题、78题都是类似的。
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
self.dfs(nums, res,[])
return res
def dfs(self, nums, res,tmp):
if not nums:
res.append(tmp)
else:
for i in range(len(nums)):
self.dfs(nums[:i]+nums[i+1:],res,tmp+[nums[i]])
79. Word Search（Medium）
Given a 2D board and a word, find if the word exists in the grid.
给定一个2维数组和一个单词，找到单词是否存在于2维数组中。
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
思路：每次遍历到错误的节点需要返回，最完美的解决办法就是回溯了，从每个节点出发判断上下左右四个节点是不是匹配word的下一个字母，如果匹配则继续dfs递归，不匹配或者超过边界则返回。
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
if not word: return True
if not board: return False
for i in range(len(board)):
for j in range(len(board[0])):
if self.dfs(board, i, j, word):
return True
return False
def dfs(self, board, i, j, word):
if not word:
return True
if i >= len(board) or i < 0 or j >= len(board[0]) or j < 0 or board[i][j] != word[0]: #匹配失败跳出递归
return False
tmp = board[i][j]
board[i][j] = '.'
if self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) or \
self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:]):
return True
board[i][j] = tmp
return False
