常用模板

一、组合（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])