一、组合（combination）
- 递归版本
def recursion(nums,start,cur,res):
# add some condition like len(cur) match some conditions
res.append(cur[:])
for i in range(start,len(nums)):
cur.append(nums[i])
recursion(nums,i+1,cur,res)
cur.pop()
return
- dfs版本
def dfs(nums,start,cur,res):
res.append(cur[:])
for i in range(start,len(nums)):
dfs(nums,i+1,cur+[nums[i]],res)
return
二、排列（permutations）
- 递归版本
def perm(nums,start,end,res):
if start == end:
res.append(nums[:])
return res
for i in range(start,end):
nums[start],nums[i] = nums[i],nums[start] # 每个元素与第一个元素交换，使得总在处理后n-1个数的全排列
perm(nums,start+1,end,res)
nums[start],nums[i] = nums[i],nums[start] # 元素交换回来
三、dfs 模板 for matrix problem
dr = [[0,1],[0,-1],[1,0],[-1,0]] # four directions
def dfs(i,j,matrix,visited,row,col,dr):
if visited[i][j]:
# return or return values
for d in dr:
ni,nj = i+d[0],j+d[1]
if x<0 or x>=m or y<0 or y>=n or other conditions: # conditions not valid
continue
visited[i][j] = True
dfs(ni,nj,matrix,visited,row,col,dr)
四、bfs模板 for matrix problem
import Queue
dr = [[0,1],[0,-1],[1,0],[-1,0]] # four directions
def bfs(matrix,dr):
que = Queue.Queue()
que.put([i,j]) # [i,j]是遍历的起点，可以是很多个点，视具体情况而定
while not que.empty():
i,j = que.get()
for d in dr:
ni,nj = i+d[0],j+d[1]
if x<0 or x>=m or y<0 or y>=n or other conditions: # conditions not valid
continue
if match some conditions:
que.put([ni,nj])
