[数据结构与算法]回溯_排列_组合 21.12.09

回溯

回溯算法又称为试探法

回溯算法针对的大多数问题有以下特点：

• 问题的答案有多个元素
• 答案需要满足一些约束
• 寻找答案的方式在每一个步骤相同

回溯算法逐步构建答案，并在确定候选元素不满足约束后立刻放弃候选元素，直到找到答案的所有元素

遍历所有排序方式

红黄蓝绿四种颜色全排列，高中升都知道是24种

方法一：暴力four循环法

def solvePermutationBadWay(array):
    solution = []
    for i in range(len(array)):
        newSolution1 = solution + [array[i]]
        newArray1 = array[: i] + array[i + 1 :]
        for j in range(len(newArray1)):
            newSolution2 = newSolution1 + [newArray1[j]]
            newArray2 = newArray1[: j] + newArray1[j + 1 :]
            for k in range(len(newArray2)):
                newSolution3 = newSolution2 + [newArray2[k]]
                newArray3 = newArray2[: k] + newArray2[k + 1:]
                newSolution4 = newSolution3 + newArray3
                print(newSolution4)
        
solvePermutationBadWay(["红", "黄", "蓝", "绿"])

可以看到有很多代码都在结构和内容上都是重复的，因此可以改写成一个函数用递归的形式调用。

方法二：回溯+递归

class Solution(object):
    def solvePermutation(self, array):
        self.helper(array, [])
    def helper(self, array, solution):
        # 递归的基线条件
        if len(array) == 0:
            print(solution)
            return
        for i in range(len(array)):
            newSolution = solution + [array[i]]
            self.helper(array[: i] + array[i + 1:], newSolution)
Solution().solvePermutation(["红", "黄", "蓝", "绿"])

这里不用newSolution变量就会出bug，solution就是全局变量

用了新变量newSolution则每一层递归的solution都是不一样的solution

46.全排列

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        # 递归需要辅助函数
        def helper(nums, solution):
            if len(nums) == 0:
                ans.append(solution)
                return 
            for i in range(len(nums)):
                # 选择一个数
                newSolution = solution + [nums[i]] 
                # 还剩多少数
                newArray = nums[: i] + nums[i + 1 :]
                # 递归
                helper(newArray, newSolution)
        helper(nums, [])
        return ans

执行用时：20 ms, 在所有 Python 提交中击败了63.06%的用户
内存消耗：13.5 MB, 在所有 Python 提交中击败了13.91%的用户

47.全排列II

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        def helper(nums, solution):
            if len(nums) == 0:
                ans.append(solution)
            used = set()
            for i in range(len(nums)):
                if nums[i] not in used:
                    newSolution = solution + [nums[i]]
                    used.add(nums[i])
                    newArray = nums[: i] + nums[i + 1:]
                    helper(newArray, newSolution)
                used.add(nums[i])
        helper(nums, [])
        return ans

执行用时：24 ms, 在所有 Python 提交中击败了88.73%的用户
内存消耗：13.6 MB, 在所有 Python 提交中击败了21.41%的用户

经典问题的组合

77.组合

选过的就不要了

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        ans = []
        def helper(array, solution):
            if len(solution) == k:
                ans.append(solution)
                return
            for i in range(len(array)):
                newSolution = solution + [array[i]]
                newArray = array[i + 1:]  # 选过的就不要再选了
                helper(newArray, newSolution)
        nums = []
        for i in range(n):
            nums.append(i + 1)
        helper(nums, [])
        return ans

执行用时：472 ms, 在所有 Python 提交中击败了11.19%的用户
内存消耗：17.1 MB, 在所有 Python 提交中击败了95.88%的用户

# 如何一行代码生成有序列表？
nums = [i for i in range(1, 10 + 1)]
Out[178]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]