我的函数库

将一些常用函数记录下来，避免重复造轮子

回溯问题

RE：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-xiang-jie-by-labuladong-2/

#回溯问题模版框架
result = []
def backtrack(当前路径，选择列表)：
	if 满足结束条件:#比如选择列表为空
    result.append(当前路径)
    return
  for 选择 in 选择列表:
    做选择（将此选择从选择列表移除）
    backtrack(当前路径，新选择列表）
    撤销选择(将上一步做出的选择从路径列表剔除，加入选择列表)

leetcode 797，77

子集问题利用回溯算法，要用 index 参数排除已选择的数字。

组合问题利用回溯思想，结果可以表示成树结构，关键点在于要用一个 index 排除已经选择过的数字。

排列问题利用回溯思想，也可以表示成树结构，关键点在于使用 contains 方法排除已经选择的数字

全排列

—新版—

排列的结束条件是选择列表的每个元素都被选择过一次

res = []
choices = [1,2,3]
curpath = []
def backtrack(curpath,choices):
    if len(choices) == len(curpath):
        res.append(curpath.copy())
        #需要传递下curpath的拷贝，否则对curpath的修改会影响到res结果
        return

    for i in range(len(choices)):
        if choices[i] in curpath:#跳过已经作出的选择
            continue #若是有放回抽样，就注释掉这个if语句
        curpath.append(choices[i])
        backtrack(curpath,choices)
        curpath.pop()
backtrack(curpath,choices)
print(res)
#[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

—旧版—–

两种方式，一种有放回的抽样，另一种是无放回抽样

比如【123】，第一种有27种结果，第二种有6种结果

#permutation，

def Permutation(ss):
    def helper(ss,resultlist,curpath="",index=0):
        #ss：str 采样字符串
        #resultlist：list，存储结果【【123】,【132】...】
        #curpath:str,当前存储的排列结果（未完成的）
        #index：int,已经进行了index位的采样
        if index == length:#到了最后一个字符
            resultlist.append(curpath)
        else:
            for i in range(len(ss)):
                #有放回抽样
                helper(ss,resultlist,curpath+ss[i],index+1)
                #无放回抽样
                #helper(ss[:i]+ss[i+1:],resultlist,curpath+ss[i],index+1)
                #ss[:i]+ss[i+1:]是为例取出当前字符ss[i]，因为是不放回采样
                #path+ss[i]是将当前字符保留到curpath中
    if not ss:
        return []
    resultlist = []
    length = len(ss)
    helper(ss,resultlist,curpath="",index=0)#list是可变对象，不必return
    return list(set(resultlist))#set()去重

print(Permutation("123"))

子集

res = []
choices = [1,2,3]
curpath = []
def backtrack(curpath,choices,index):
    #当前路径，选择列表，已经选了index个
    res.append(curpath.copy())

    for i in range(index,len(choices)):
        curpath.append(choices[i])
        backtrack(curpath,choices,i+1) #注意是i+1
        curpath.pop()
backtrack(curpath,choices,index=0)
print(res)
#[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

组合

组合与子集差不多，区别在于结束条件，组合和排列必须是树的叶子结点

res = []
choices = [1,2,3,4]

def backtrack(curpath,choices, index, k):
    if len(curpath) == k:
        res.append(curpath.copy())
        return
    for i in range(index, len(choices)):
        curpath.append(choices[i])
        backtrack(curpath.copy(),choices,i+1, k)
        curpath.pop()

backtrack(curpath=[],choices=choices,index=0,k=3)
print(res)
#[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]