Did you know that you can navigate the posts by swiping left and right?

回溯算法

10 Sep 2022 . category: tech .

算法简介

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

算法模板

def Solution():
	res = [] # 可行结果集
	def backtracking(v=[]):
		if (required): # 满足条件
			res.append(v)
			return
		if (beyond): # 超过边界
			return
		for k in feasible_set: # 遍历可行集合
			backtracking(v + [k]) # 尝试k，进行下一步求解
	backtracking()
	return res

def Solution():
	res = [] # 可行结果集
	def backtracking(v=[]):
		if (required): # 满足条件
			res.append(v[:])
			return
		if (beyond): # 超过边界
			return
		for k in feasible_set: # 遍历可行集合
			v.append(k)
			backtracking(v) # 尝试k，进行下一步求解
			v.pop()
	backtracking()
	return res

例1：力扣46. 全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：
输入：nums = [1]
输出：[[1]]

例1题解

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        def backtracking(v=[]):
            if len(v) == len(nums):
                res.append(v)
                return
            for i in nums:
                if i not in v:
                    backtracking(v + [i])
        backtracking()
        return res

例2：力扣17. 电话号码的字母组合

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

示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：
输入：digits = ""
输出：[]

示例 3：
输入：digits = "2"
输出：["a","b","c"]

例2题解

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dic = {'2':"abc",'3':"def",'4':"ghi",'5':"jkl",'6':"mno",'7':"pqrs",'8':"tuv",'9':"wxyz"}
        res = []
        if digits == "":
            return res
        def backtracking(nums, s = ""):
            if nums == "":
                res.append(s)
                return
            for n in dic[nums[0]]:
                backtracking(nums[1:], s + n)
        backtracking(digits)
        return res