关于回溯问题中的排列问题的思考（LeetCode46题与47题）

1.配置环境

使用环境：python3.7
平台：Windows10
IDE：PyCharm

2.博客由来

博主在做刷LeetCode时对于其中全排列问题有一点思考，在此记录一下。

3.问题描述

排列、组合问题中十分关键的问题在于去重，常用的方法是采用used数组进行去重，但是这个或许并不是最优的方法，以LeetCode46题为例

4.常见的方法

以代码随想录提供的方法为例
方法一：采用usage_list数组进行记录，每次进入回溯（backtracking）是就行判断改元素是否使用，从而实现去重。

class Solution:
    def __init__(self):
        self.path = []
        self.paths = []

    def permute(self, nums: List[int]) -> List[List[int]]:
        usage_list = [False] * len(nums)
        self.backtracking(nums, usage_list)
        return self.paths

    def backtracking(self, nums: List[int], usage_list: List[bool]) -> None:
        # Base Case本题求叶子节点
        if len(self.path) == len(nums):
            self.paths.append(self.path[:])
            return

        # 单层递归逻辑
        for i in range(0, len(nums)):  # 从头开始搜索
            # 若遇到self.path里已收录的元素，跳过
            if usage_list[i] == True:
                continue
            usage_list[i] = True
            self.path.append(nums[i])
            self.backtracking(nums, usage_list)     # 纵向传递使用信息，去重
            self.path.pop()
            usage_list[i] = False

方法二：丢掉usage_list，用self.path中的记录代替，但是去重的思想还是在于判断num[i]是否出现在记录中，是的话就continue掉

class Solution:
    def __init__(self):
        self.path = []
        self.paths = []

    def permute(self, nums: List[int]) -> List[List[int]]:
        self.backtracking(nums)
        return self.paths

    def backtracking(self, nums: List[int]) -> None:
        # Base Case本题求叶子节点
        if len(self.path) == len(nums):
            self.paths.append(self.path[:])
            return

        # 单层递归逻辑
        for i in range(0, len(nums)):  # 从头开始搜索
            # 若遇到self.path里已收录的元素，跳过
            if nums[i] in self.path:
                continue
            self.path.append(nums[i])
            self.backtracking(nums)
            self.path.pop()

5.我的思考

思路：
无论是使用usage_list还是self.path都在于通过一个容器记录元素使用情况，在进行递归时，对所有元素进行一次判断，针对元素使用过的情况作出continue操作。

或许有更为直接的去重方法，通过控制进入backtracking的nums数组，直接对nums数组进行去重，让传入backtracking的nums就已经被去重了，在使用for进行层间遍历时，可以直接跳过被使用的元素，具体操作如下：

# author:Hurricane
# date: 2022/7/2
# E-mail:[email protected]


class Solution:
	def permute(self, nums):
		self.path = []
		self.res = []
		self.backtracking(nums, len(nums))
		return self.res

	def backtracking(self, nums, length):
		if len(self.path) == length:
			self.res.append(self.path[:])
			return

		for i in range(len(nums)):
			self.path.append(nums[i])
			self.backtracking(nums[0:i] + nums[i + 1:], length)
			self.path.pop()

核心代码在于

self.backtracking(nums[0:i] + nums[i + 1:], length)

这行代码控制了进入backtracking的元素，直接从进入backtracking的源头完成去重，

6.其他类似的题目

对于LeetCode47题也可以用同样是思路进行

这里也贴出博主思考的方法

# author:Hurricane
# date: 2022/7/2
# E-mail:[email protected]


class Solution:
	def permuteUnique(self, nums):
		self.path = []
		self.res = []
		nums.sort()
		self.backtracking(nums, len(nums))
		return self.res

	def backtracking(self, nums, length):
		if len(self.path) == length:
			self.res.append(self.path[:])
			return

		for i in range(len(nums)):
			if i > 0 and nums[i] == nums[i - 1]:
				continue
			self.path.append(nums[i])
			self.backtracking(nums[0:i] + nums[i + 1:], length)
			self.path.pop()

7.参考文献

1. 代码随想录全排列
2. 代码随想录排列问题（二）

8.结束语

如果本文对你有帮助的话还请点赞、收藏一键带走哦，你的支持是我最大的动力！(づ｡◕ᴗᴗ◕｡)づ