Python算法：DFS排列与组合算法（手写模板）

自写排列算法：

例：前三个数的全排列（从小到大）

def dfs(s,t):if s==t:   #递归结束，输出一个全排列print(b[0:n])else:for i in range(t):if vis[i]==False:vis[i]=Trueb[s]=a[i]   #存排列dfs(s+1,t)vis[i]=Falsea=[1,2,3,4,5,6,7,8,9]
b=[0]*10   #记录生成的一个全排列
vis=[False]*10  #记录第 i 个数是否用过
n=3
dfs(0,n)   #前 n 个数的全排列 

1 2 3 4 5 的全排列，第1个空格有5种填充方法，相当于第一个数和后面的5-1个数分别做了一次交换。
那么第一个空格的所有情况已经求出来了，同理，在第1个空格的基础上，第2个空格有n-1种填充方法，相当于第2个数和后面的5-2个数分别做了一次交换。

所以我们可以先把以1开头的全排列情况全部求出来，再求以2、3、4、5的，在以1开头的前提下，我们再以2开头，层层递归下去，值得注意的是，交换以后我们需要再交换回来；

 有3个盒子 1、2、3，3张扑克牌 1、2、3，进行扑克牌全排列可以这样实现：
不管面对哪个盒子，都尝试按“1--n”的顺序将扑克牌放入，如果第m张扑克牌已经用过，判断第m+1张是否可用。
当放满n个盒子时，回头，把盒子里面的牌捡回来，再继续按顺序放牌进盒子。

 过程：
第1个盒子：放入1号牌
第2个盒子：本来应该放入1号牌，但是由于1号牌已用，只能按顺序放入2号牌
第3个盒子：本来应该放入1号牌，但是1号牌已用，而且判断2号牌也已用，只能放入3号牌
盒子放满，输出
回头，捡回第3个盒子的牌；
第3个盒子：由于手里只有3号牌，放不了了，只能再回头
第2个盒子：捡回2号牌，此时手里剩2、3号牌，对于第2个盒子，按顺序放牌、现在可以将3号牌放入。
第3个盒子：重新按“1--n”的顺序放牌，所以放入2号牌
回头......

打印 n 个数中，任意 m 个数的排列

        4个数中，任意3个数的排列

def dfs(s,t):if s==3:   #递归结束，输出一个全排列print(b[0:3])else:for i in range(n):if vis[i]==False:vis[i]=Trueb[s]=a[i]   #存排列dfs(s+1,t)vis[i]=Falsea=[1,2,3,4,5,6,7,8,9]
b=[0]*10   #记录生成的一个全排列
vis=[False]*10  #记录第 i 个数是否用过
n=4
dfs(0,n)   #前 n 个数的全排列

自写组合算法：

        1、例：打印二进制数，以打印000~111为例（若需要反过来打印，只需交换第8、10行）

vis=[0]*10
def dfs(k):  #深搜到第 k 个if k==3:for i in range(3):print(vis[i],end='')print( )else:vis[k]=0   #不选第 k 个dfs(k+1)   #继续搜下一个vis[k]=1   #选第 k 个dfs(k+1)   #继续搜下一个
dfs(0)

        2、例：打印组合，以3个数{ 1，2，3 }为例

def dfs(k):  #深搜到第 k 个if k==3:for i in range(3):if vis[i]==1:print(a[i],end='')print( )else:vis[k]=0   #不选第 k 个dfs(k+1)   #继续搜下一个vis[k]=1   #选第 k 个dfs(k+1)   #继续搜下一个
vis = [0] * 10
a=[1,2,3,4,5,6,7,8,9,10]
dfs(0)