leetcode_回溯算法_python

该类问题的核心:递归过程都在“全局”变量里记录，for（横向的选择）都在递归函数里记录。

主要问题类型：排列问题，组合问题，子集问题，子序列，分割问题，其他NP问题

常用剪枝使得不重复：如果结果不要求次序与原list相对次序相同（组合，子集，排列）问题，则先将list排序再判断是否与前一个相同；如果解雇要求次序（子序列）问题，不能排序list，则在回溯函数中存一下已经通过的元素值，判断是否用过。

leetcode77.组合

C(n,k)类问题，类似的问题先想手动解决的过程，容易发现下一轮的起始位置向后移，所以回溯算法需要一个i_start参数。

该题可以剪枝：在某一轮中，如果已经选择的数的数量len(path)加上下次待选集合的大小(len(i,n+1))比需要的数量还小，则打破循环。

leetcode216.组合总和3

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。因此数量为规定数量时返回，在此情况下如果和为规定和，则更新结果。该问题可以剪枝：当path的和已经大于规定和时，直接返回。

leetcode40.组合总和2

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。因为前面一个相同的比后面的选择多（多一个相同的），所以前面所有可能必然包括后面，所以去掉后面所有相同的。每一层中横向剪枝（即有共同父节点的横向不能选相同数值的选项）。为了方便剪枝，在开始时对candidates进行排序，使得相同的数值放在一起。

leetcode39.组合总和

需要重复做。给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。同样的，为避免子集间重复，设置i_start使得for横向剪枝，又因为下一次选择时可以重复选择上一次选择的元素，所以i_start = i。

剪枝：可以先将candidates排序，当for中和大于target时，无需继续，break。

leetcode17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射与电话按键相同，注意 1 不对应任何字母。

通过字典将数字和字母组合存一下，方便查找本轮可能的组合（即for这一方向）。backtracing传入当前处理数字的下标，当下标刚超出长度时存结果并return。每一论中的选择集合通过字典找出来，根据该集合写for。

leetcode131.分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串，返回 s 所有可能的分割方案。主要思路：横向的for探查以i_start为头的所有回文串（即可选选择），递归其后面一个为起始的回文情况。特别要注意返回条件，当起始i_start等于len(s)时，没有起始点可选，则返回。在for中，注意i的区间和截取子串的区间需要照应。

class Solution:
    def isPalindrome(self, s):
        return s == s[::-1]
    def partition(self, s: str) -> List[List[str]]:
        #横向延长区间，在已找到的回文串基础上开始探讨可能，即先切割一个，再添加剩下的可能性
        #for循环内非常容易错 因为range左闭右开，所以如果右边取len(s)，则说明i最大可以取len(s)-1，所以子串为左闭右闭[i_start, i]，所以取子串时取s(i_start, i+1)，下次开始也是i+1
        res = []
        path = []

        def backtracing(s, i_start):
            if i_start == len(s):
                res.append(copy.copy(path))
                return
            
            for i in range(i_start, len(s)): #注意 非常容易错 因为右端值不会取到 所以要取len(s) 字符串区间为[i_start:i],所以i至少要取到len(s)-1，所以最后到len(s)
                if self.isPalindrome(s[i_start:i+1]):
                    path.append(s[i_start:i+1])
                else:
                    continue #注意是continue 不是break 因为往后可能是回文
                
                backtracing(s, i+1)
                path.pop()
        backtracing(s, 0)
        return res

 leetcode93.复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。主要想法：返回条件设置为path有三个的时候，检查剩余的是否符合条件，符合则存到结果中并返回，不符合直接返回。注意在合并时只有列表可以连起来，所以要把字符串转换成列表。此外，虽然题面上说了整数，但如果面试遇到要问一下输入的限制，是否需要检查。

class Solution:
    def isValid(self, s):
        if not s:
            return False
        if s[0] == ‘0‘ and len(s) > 1:
            return False
        
        if int(s) <= 255:
            return True
    

    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        path = []
        len_s = len(s)
        candidates = [‘0‘, ‘1‘,‘2‘,‘3‘,‘4‘,‘5‘, ‘6‘,‘7‘, ‘8‘,‘9‘]
        for i in range(len(s)):
            if s[i] not in candidates:
                return []
        
        def backTracing(i_start):
            if i_start >= len_s:
                return
            if len(path) == 3:
                if self.isValid(s[i_start:]):
                    res.append(‘.‘.join(path+[s[i_start:]])) #注意 只有列表相加
                return
            
            for i in range(i_start,len_s):
                if self.isValid(s[i_start: i+1]):
                    path.append(s[i_start: i+1])
                else:
                    continue
                backTracing(i+1)
                path.pop()
        backTracing(0)
        return res

 leetcode78.子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集。区别于组合类问题，子集类问题的每个节点都是解，所以所有节点都要存在结果中，存下后再判断是否需要返回。其实不反回也没问题，因为输入的i是有限的。易错点：如果要写返回，则判断i_start == len(s)，因为i_start表示该循环待处理的点，所以应当是len(s)时返回而非len(s)-1(此时则还有一个点待处理）。

leetcode90.子集2

区别于78，该题中整数数组含有重复元素。则每个子集内可以有重复元素，但没有重复子集。因此需要在for循环处剪枝，先对序列进行排序再进行剪枝。同样的，子集类问题每个节点都是结果，所以在每个节点都需要保存。

leetcode491.递增子序列

首先一个容易错的点：子序列和子串

一个字符串 ss 被称作另一个字符串 SS 的子串，表示 ss 在 SS 中出现了。

一个字符串 ss 被称作另一个字符串 SS 的子序列，说明从序列 SS 通过去除某些元素但不破坏余下元素的相对位置（在前或在后）可得到序列 ss 。

 参考：https://www.cnblogs.com/miserweyte/p/11681350.html

因为要求是子序列，所以不能破坏相对位置，在开始的时候不能进行排序。重新思考该问题，即找到有序的子集，子集不能重复且子集内递增。递增比较容易处理，需要注意的点是在存结果时要先判断序列长度是否大于等于2。子集不能重复，即需要对for循环剪枝，则每一层（即在回溯函数内部）用一个数组记录已经用过的数，每次做选择时判断一下该数是否用过。

leetcode46.全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

排列问题相较于组合问题，相当于每次选择时不能选择path上的数字， 或可以通过每次将序列除了自己的部分传递到回溯函数内作为选择。

leetcode47.全排列2

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

相较于46，该问题的序列包含重复数字。因为全排列不需要与原序列的相对位置相同，所以先将nums排序，再通过for循环剪枝（i>0且判断是否与上一个一样）。

leetcode332.重新安排行程

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

提示：

• 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
• 所有的机场都用三个大写字母表示（机场代码）。
• 假定所有机票至少存在一种合理的行程。
• 所有的机票必须都用一次 且 只能用一次。

从提示中可以分析出几个关键点：1.同一个出发点的机票需要排序。2.每张机票只能使用一次，所以需要记录是否用过。3.每张机票必须使用一次，所以可以确定回溯的返回条件。

主要思路：用defaultdict(list) (默认返回为空列表）存机票信息，并排序。存机票信息时可以将使用信息记录一下。

易错点：1.path以[‘JFK‘]初始化，非空。2.修改是否使用信息时考虑一下深浅拷贝和直接赋值的问题，防止没有修改成功。3.重点重点重点！！！只需要一个解，所以res一旦非空就break，事实上只有第一个找到的解是符合题意的，后面会覆盖。修改res时声明nonlocal后使用浅复制。

leetcode51.N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。攻击：不能一排，不能一列，不能同斜线。

思路：每次将一个棋子放在一排中，递归下一排（所以不需要检查是否共排）。注意需要注意一下输入输出的格式，和检查是否成立的函数需要输入放置棋子的坐标（i，j）

leetcode_回溯算法_python

原文：https://www.cnblogs.com/leetcodesumup/p/14397502.html