每日一道算法之--回溯算法总结和全排列问题

回溯

Word count: 725Reading time: 3 min

 2020/03/26   Share

回溯算法

“回溯”算法也叫“回溯搜索”算法，主要用于在一个庞大的空间里搜索我们所需要的问题的解。我们每天使用的“搜索引擎”就是帮助我们在庞大的互联网上搜索我们需要的信息。“搜索”引擎的“搜索”和“回溯搜索”算法的“搜索”意思是一样的。

“回溯”指的是“状态重置”，可以理解为“回到过去”、“恢复现场”，是在编码的过程中，是为了节约空间而使用的一种技巧。而回溯其实是“深度优先遍历”特有的一种现象。之所以是“深度优先遍历”，是因为我们要解决的问题通常是在一棵树上完成的，在这棵树上搜索需要的答案，一般使用深度优先遍历。

回溯算法的模板:

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

这个模板适合许多利用回溯方法解决的问题，如全排列，组合总和，子集等问题。

全排列

力扣第46题： https://leetcode-cn.com/problems/permutations/

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

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

利用回溯解决

可以看出,输入的数组中,所有元素排列组合,每一个元素都有可能在第一位,第二位……第N位,所以可以通过回溯算法,将所有的可能都列举出来。

创建一个列表res保留结果,构建回溯函数,参数分别为保留当前组合的列表 combination, 以及剩下的元素；
当剩下的元素为0时,证明所有元素都已经考虑进去了,就可以将该组合加进res中；
当剩下的元素不为空时,证明组合还没有结束,继续往下一层考虑。

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

复杂度分析

全排列II

力扣第47题 : https://leetcode-cn.com/problems/permutations-ii/

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

示例:

输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        # 排序去重
        nums.sort()
        def backtrack(tmp, nums):
            if not nums:
                res.append(tmp)
            for i in range(len(nums)):
                # 去重
                if i > 0 and nums[i] == nums[i -1]:
                    continue
                backtrack(tmp + [nums[i]], nums[:i] + nums[i+1:])
        backtrack([], nums)
        return res