[数据结构与算法]回溯算法 leetcode 新

回溯法抽象为树形结构后，其遍历过程就是：「for循环横向遍历，递归纵向遍历，回溯不断调整结果集」。

回溯算法一般的代码形式：

def backtrack(参数)：

? ? ? ? if 终止条件：

? ? ? ? ? ? ? ? 更新结果集

? ? ? ? ? ? ? ? return

? ? ? ? for （选择本层集合中的元素）：

? ? ? ? ? ? ? ? 处理节点

? ? ? ? ? ? ? ? backtrack(路径，选择列表) //递归

77. 组合

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        if k > n:
            return []
        res = []
        # path = []
        def backtrack(startindex, n, k, path):
            if len(path) == k: #终止条件
                res.append(path)  #存放结果
                return
            for i in range(startindex, n + 1): #startindex是确认起始的位置，之前用过的数不会参与到下一步的遍历中
                backtrack(i + 1, n, k, path + [i])
            return

        backtrack(1, n, k, [])
        return res

?216. 组合总和 III

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        res = []
        def backtrack(startindex, n, k, path):
            if len(path) == k:
                if sum(path) != n:
                    return
                else:
                    res.append(path)
                    return
            if sum(path) > n:
                return
            for i in range(startindex, 10):
                backtrack(i + 1, n, k, path + [i])
            return
        backtrack(1, n, k, [])
        return res

17. 电话号码的字母组合

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        phone = {
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z']
    }

        def backtrack(combination, nextdigits):
            if len(nextdigits) == 0:
                res.append(combination)
                return
            
            for letter in phone[nextdigits[0]]:
                backtrack(combination + letter, nextdigits[1:])
        res = []
        if not digits:
            return []
        backtrack('', digits)
        return res

39. 组合总和? (自己严格按照回溯格式写出来的，但是效率很低)

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        res = []
        def backtrack(startindex, target, path):
            if sum(path) == target:
                res.append(path)
                return
            elif sum(path) > target:
                return
            for i in range(startindex, len(candidates)):
                backtrack(i, target, path+[candidates[i]])
            return
        backtrack(0, target, [])
        return res

?