基础算法题总结2--回溯法相关

回溯法(递归的一种)

回溯算法的递归使用以及剪枝策略。
回溯法：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。

正规写法：

t = []
def dps(cur,n):## cur表示当前位置，n表示原序列长度
    if cur == n:
        ## 保存答案
        ## 这里保存答案的时候需要考虑的是不能直接保存t的值，而是需要t.copy(),
        ## 否则当t改变的时候，保存的内容也是会改变的
        ## 【值传递和引用传递、深拷贝和浅拷贝】，需要深拷贝
        return
    t.append(cur) ## 考虑当前被选中
    dps(cur+1,n)
    t.pop()  ## 考虑当前没有被选中
    dps(cur+1,n)
dps(0,n)

简便写法：

def dps(i,tmp): ## i表示当前的位置，tmp列表，临时列表，选中则放入，不选中则返回
    ## 保存答案
    for j in range(i,n): ## 后部分
        dps(j+1, tmp + j) ## 从空到全，j表示选中的位置，可以改用此选中位置的数
dps(0,[])

如果涉及剪枝或避免重复元素：

1. 先进行排序，保证重复的元素放在一起
2. 然后回溯选取下一个节点的时候判断一下是否和前面的相同，相同的则不用再继续遍历，相当于剪枝；不同则要继续遍历。

简便写法：

nums.sort() ## 需要先进行排序
def dps(i,tmp): ## i表示当前的位置，tmp列表，临时列表，选中则放入，不选中则返回
    ## 保存答案 深拷贝
    for j in range(i,n): ## 后部分
        if j > i and nums[j] == nums[j-1]:  
        ## 判断当前要选中的这个元素是否和上一个选中的一样，如果一样则略过不用遍历
            continue
        dps(j+1, tmp+ [nums[j]]) ## 从空到全，j表示选中的位置，可以改用此选中位置的数
dps(0,[])

值传递、引用传递、浅拷贝、深拷贝

值传递和引用传递

不可变类型在传递参数时都是传值形式，如int,str,tuple类型。
可变类型在传递参数时都是引用传递，如list,set,dict类型。指向的都是同一块内存地址

值传递：当元素被赋予新值或者修改值的时候，是指向了一个新的对象，和原对象无关。当原值没有对象再指向它，就会被python的GC回收。
引用传递：指向的都是同一块内存地址，一旦改变值，所有指向这个内存地址的都会改变

拷贝的内置函数
copy()浅拷贝：不拷贝对象的内容，只拷贝子对象的引用，原数据改变，则子对象会改变
deepcopy()深拷贝：对子对象的内存也会拷贝一份，对子对象的修改不会影响源对象，原始数据的改变不会影响深拷贝

a = b: 引用传递
a.copy()：浅拷贝
copy.copy(a)：浅拷贝
copy.deepcopy(a)：深拷贝

区别nums和nums[:]
nums[:] = nums[0:len(nums)] 可以使用[:]来拷贝全部元素
nums[:]在计算机中是新分配了一个地址，当其改变时是不会影响到原数据的，相同的是原数据的改变也不会影响数值的改变。

相关练习

LeetCode中相关的题目：

• 78.子集: 可以使用回溯法，时间复杂度为O(n*2^n),空间复杂度为O(n).
• 90.子集 II:解集不能包含重复的子集（回溯算法+剪枝）
• 46.全排列：回溯法，划分左右
• 47.全排列II：回溯法+剪枝，可以使用标记列表和回溯相结合(以空间换时间)

题目详细描述

子集

class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:   
    n = len(nums)
    res = []
    def dps(i,tmp): ## 回溯法
        res.append(tmp)
        for j in range(i, n):
            dps(j + 1, tmp + [nums[j]])            
    dps(0, [])
    return res

子集II

class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
    res = []
    n = len(nums)
    nums.sort() ## 先排序
    def dps(i, tmp): ## 回溯算法
        res.append(tmp)
        for j in range(i,n):
            if j > i and nums[j] == nums[j-1]: ## 判断剪枝
                continue
            dps(j+1, tmp + [nums[j]])      
    dps(0, [])
    return res

全排列：将题目给定的数组划分成左右两个部分，左边表示已经填过的数，右边表示代填的数，在回溯的时候动态维护这个数组

class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
    res = []
    n = len(nums)
    def back(cur): ## 假设填到第cur个位置
        if cur == n: ## 所有的数都填完了
            res.append(nums[:]) ## 使用[:]来拷贝全部元素
            return 
        for i in range(cur ,n): ##[0,cur-1]是已经填过的数，[cur,n-1]是代填的数
            ## 尝试使用[cur,n-1]里面的数来填cur下标当前位置上的数
            nums[cur],nums[i] = nums[i],nums[cur] ## 动态维护数组(i表示要代填的数的下标，cur表示要填的位置的下标，两个进行交换，则[0,cur]部分就成了已填过的数)
            back(cur+1)  ## 继续递归填下一个数 [cur+1,n-1]
            nums[i],nums[cur] = nums[cur],nums[i] ## 撤销
    back(0) ## 从头开始填充
    return res

全排列II：

class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    n = len(nums)
    nums.sort() ## 排序是剪枝的前提
    res=[]
    mark = [0 for i in range(n)] ## 标记
    def back(cur,t): ## 回溯函数
        if cur == n:
            res.append(t.copy())
            return 
        for i in range(n):
            ## 剪枝 1.当前已经被标记，则不需要再使用 
            ## 2.如果当前和前一个元素相同，且前一个元素未被标记
            if mark[i] == 1:
                continue
            ## i>0保证nums[i-1]是有意义的
            ## mark[i-1] == 0 也可以写成 not mark[i-1] 
            ## mark[i-1]在深度优先遍历的过程中刚刚被撤销选择
            if i>0 and nums[i]==nums[i-1] and mark[i-1] == 0:
                continue
            ## 回溯前
            t.append(nums[i])
            mark[i] = 1
            ## 递归
            back(cur+1,t)
            ## 回溯后              
            t.pop()
            mark[i] = 0
    back(0,[])
    return res