DFS算法
DFS算法，又可以称为回溯算法
回溯不是指程序执行完成后，goto到某段程序，而是指在当前局面下，有多种选择，依次尝试所有的选择，直到所有选择就被尝试过，或者遇到合适的终止条件为止。
每次做一个选择，可能会影响后续的选择，所有每个选择都有限定的条件(有可能与前一个选择无关，也可能与前一个选择有关)。
DFS的执行是递归的方式，所以在执行DFS之前，首先需要考虑清楚每次递归的参数选择。
做DFS题目，只要明确三点就行：
- 选择 (Options)，
- 限制条件 (Restraints)，
- 结束条件 (Termination)。
在DPS中，需要理解递归和遍历，一般来说，使用递归达到"终止条件", 使用遍历实现"尝试所有可能"的选择。
如果"选择"是可以枚举的，可以直接枚举，遍历遍历树的左右子树之类的操作
Letter Combinations of a Phone Number
# 分析：
buttons = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
选择: 比如输入是“23”，第一次选择2， 字符串是abc, 此时有三种选择:a, b, c,
第二次选择3，字符串是def，也有三种选择,
选择限制:是不能超过字符串的长度。
结束条件: "23" 每个字符串对应的数据都被选择了，就表示结束
class Solution(object):
def letterCombinations(self, digits):
if not digits:
return []
ans = []
buttons = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
self.dfs(0, '', digits, buttons, ans)
return ans
def dfs(self, i, s, digits, buttons, ans):
# i从0开始先选择2， 然后在选择3，结束条件是23都选择完成
if i == len(digits):
ans.append(s)
return ans
# 第一种选择有abc
for c in buttons[int(digits[i])]:
self.dfs(i + 1, s + c, digits, buttons, ans)
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
分析:
1. 什么都不选, 那可以选择的数分别是1, 2, 3
2. 选择1，返回[1], 选择1之后，还可以选择2，选择2之后，还可以选择3
3. 选择2. 选择2之后，还可以选择3
4. 选择3, 后面没有数据可以选择了
选择限制条件: 1. 不能超过数组长度，2. 一个数前面选择了，后面就不能再选了，做出一个选择后, 还可以选择的数是 range(i+1, len(nums))
结束条件: 不得大于数组长度
结果: 保存所有遇到的选择项
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans, path = [], []
self.dfs(0, nums, path, ans)
return ans
# i=0开始，path=[], 第一次调用选择是[]
# 选择完空后，还可以做得选择是xrange(0, len(nums))
def dfs(self, i, nums, path, ans):
ans.append(path)
# 当i == len(nums), xrange为终止执行
for i in xrange(i, len(nums)):
# 不能使用path.extend([nums[i]]), 只能使用path + [nums[i]]，不能改变path的值
self.dfs(i + 1, nums, path + [nums[i]], ans)
Example:
# 有重复的数
Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums:
return []
ans, path = [], []
nums.sort()
self.dfs(0, path, nums, ans)
return ans
def dfs(self, i, path, nums, ans):
ans.append(path)
for j in xrange(i, len(nums)):
if j > i and nums[j] == nums[j - 1]:
continue
self.dfs(j + 1, path + [nums[j]], nums, ans)
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
path, ans = [], []
self.dfs(1, k, n + 1, path, ans)
return ans
def dfs(self, i, k, n, path, ans):
if len(path) == k:
ans.append(path[:])
return
for j in xrange(i, n):
self.dfs(j + 1, k, n, path + [j], ans)
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
ans, path = [], []
candidates.sort()
self.dfs(target, 0, path, ans, candidates)
return ans
def dfs(self, target, i, path, ans, nums):
if target == 0:
ans.append(path)
return
if target < nums[0] or i >= len(nums):
return False
从子集合里面各取一个数，可以组成多少子集合
Example:
Input: nums = [[1, 2, 3], [4], [7, 6]]
Output: [[1, 4, 7], [1, 4, 6], [2, 4, 7], [2, 4, 6], [3, 4, 7], [3, 4, 6]]
分析：
选择: 依次选择数组里面的子数组
选择限制: 每次选择给子数组后，这个子数组可以选择的数不得超过数组长度
结束条件: 不得超过最外层最大数组的长度
结果: 保存每次选择完成的数据
def combination(nums):
ans, path = [], []
dfs(nums, 0, path, ans)
return ans
def dfs(nums, i, path, ans):
if i == len(nums):
# 这里千万不能使用path, 因为list是可变的
ans.append(path[:])
return
for item in nums[i]:
path.append(item)
dfs(nums, i + 1, path, ans)
# 这一定要退出
path.pop()
Convert Sorted Array to Binary Search Tree
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
分析：题目是生成一个平衡数，平衡数的两边的深度不得大于1，如果root节点，在数组的中间，则可以保证两边的数深度不会超过1
如何构建一棵树，首先构建一个节点，然后尝试构建这个节点的左子节点和右子节点，然后尝试构建左子节点的左子节点和右子节点，在尝试构建右子节点的左子节点和右子节点，依次递归下去。
思路误区：构建一个节点后，可以立马构建节点的子节点，这是不对的，子节点的构建递归的，依赖于递归函数的返回值。只有递归完成了，第一个节点的子节点才算构建完成。
选择: 首先，可以选择数组的中间的一个值作为节点，然后选择左节点，在选择右节点
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
return self.dfs(0, len(nums) - 1, nums)
def dfs(self, left, right, nums):
if left > right:
return None
mid = (left + right) // 2
root = TreeNode(nums[mid])
# 先构造做节点
root.left = self.dfs(left, mid - 1, nums)
# 在完成右节点的构造
root.right = self.dfs(mid + 1, right, nums)
return root
验证是否是二叉搜索树，左子节点都小于root， 右子节点都大于root
Input:
2
/ \
1 3
Output: true
# 分析：
判断一个树是否是Binary Tree，需要判断左子树和右子树都是Binary Tree，
所以需要依次递归所有的子树，保证每个子树都是Binary Tree
选择: 有左右两个选择
限制条件:
class Solution(object):
def isValidBST(self, root, lessThan=float("inf"), largerThan = float('-inf')):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
if root.val >= lessThan or root.val <= largerThan:
return False
return self.isValidBST(root.left, min(root.val, lessThan), largerThan) and \
self.isValidBST(root.right, lessThan, max(root.val, largerThan))
Input:
11110
11010
11000
00000
Output: 1
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
def sink(i, j):
# 比如是[1,1,1,0,1], i= 0, j = 0, grid[i][j] = 1
# 满足递归条件，直到grid[i][j] == 0, 不满足递归条件了，不再调用map函数，也就是终止递归了
# 潜意识的停止递归常常使用return，记住还有这种方式
if 0 <= i < len(grid) and 0 <= j < len(grid[i]) and grid[i][j] == '1':
grid[i][j] = '0'
map(sink, (i+1, i-1, i, i), (j, j, j+1, j-1))
# 如果发现了有个1，则返回1
return 1
return 0
return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[i])))
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
关键点是：最外层的O一定不会被包围，所以只需要选择最外层的O, 然后找到和O相关的O，并标记
class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: None Do not return anything, modify board in-place instead.
"""
if not board:
return
m, n = len(board), len(board[0])
for i in range(m):
if board[i][0] == 'O':
self.dfs(i, 0, board)
if board[i][n - 1] == 'O':
self.dfs(i, n - 1, board)
for j in range(n):
if board[0][j] == 'O':
self.dfs(0, j, board)
if board[m - 1][j] == 'O':
self.dfs(m - 1, j, board)
for i in range(m):
for j in range(n):
if board[i][j] != 'N':
board[i][j] = 'X'
else:
board[i][j] = 'O'
def dfs(self, i, j, board):
m, n = len(board), len(board[0])
if 0 <= i < m and 0 <= j < n and board[i][j] == "O":
board[i][j] = 'N'
self.dfs(i + 1, j, board)
self.dfs(i - 1, j, board)
self.dfs(i, j + 1, board)
self.dfs(i, j - 1, board)
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.
# 注意不能往回走，所以走过的坐标必须标记一下
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
if not board or not word:
return board and word
m, n = len(board), len(board[0])
for i in range(m):
for j in range(n):
if self.dfs(i, j, board, word):
return True
return False
def dfs(self, i, j, board, word):
if len(word) == 0:
return True
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[0]:
return False
# bad case: board = [['a', 'a']] word = 'aaa', 这种情况不能往回走，必须标记
tmp = board[i][j]
board[i][j] = '#'
res = self.dfs(i+1, j, board, word[1:]) or self.dfs(i - 1, j, board, word[1:]) or self.dfs(i, j + 1, board, word[1:]) or self.dfs(i, j - 1, board, word[1:])
board[i][j] = tmp
return res
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Return:
[
[5,4,11,2],
[5,8,4,5]
]
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
if not root:
return []
ans, path = [], []
def dfs(root, sum, ans):
if not root:
return
path.append(root.val)
sum -= root.val
if not root.left and not root.right:
if sum == 0:
# path只能使用[:]
ans.append(path[:])
dfs(root.left, sum, ans)
dfs(root.right, sum, ans)
# 做下一个选择之前，需要清除掉本次选择append的数
path.pop()
dfs(root, sum, ans)
return ans
"""
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
分析: 如果n=3表示“(”有3个, 第一次必须选择一个"(", 选择完成后，"("还可以用的个数是2，此时，程序可以接着画"(", 或者画")", 所以程序有两种选择
选择限制: 一共只有3个"(", 所以不能超出这个限制
"""
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
ans = []
self.dfs(n, 0, '', ans)
return ans
# left, right 还可以用的括号，最开始right有3个，left有0个
def dfs(self, right, left, cur, ans):
# 左边和右边的可用的都用完了
if not right and not left:
ans.append(cur)
if right > 0: self.dfs(n - 1, left + 1, cur + '(', ans)
if left > 0: self.dfs(n, left - 1, cur + ')', ans)