【回溯】全排列 II leetcode47

小风_

于 2022-06-06 23:41:34 发布

阅读量263

点赞数

分类专栏：算法题文章标签： leetcode 算法数据结构

本文链接：https://blog.csdn.net/qq_33952811/article/details/125156715

版权

算法题专栏收录该内容

22 篇文章

订阅专栏

本文介绍了如何解决LeetCode上的Permutations II问题，即给定一个可能含有重复数字的序列，找出所有不重复的全排列。通过排序和剪枝技巧实现，对于每个数字，如果它与前一个数字相同，则跳过，避免重复。算法主要步骤包括排序、递归遍历并去重，最后返回所有不重复的排列组合。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。示例 1：输入：nums = [1,1,2] 输出：
[[1,1,2], [1,2,1], [2,1,1]] 示例 2：输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
链接：https://leetcode.cn/problems/permutations-ii

思路：和lc46不一样的地方在于，含有重复数字，此时，借鉴数组总和II的思路，首先讲序列进行排序，然后每次遍历的时候for循环判断下一个数字是否和上一个相同，相同的自动忽略（剪枝）掉，以此达到去重的目的

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.ret = []

        '''NOTE
        1.思考递归树（根节点和中间节点是什么）
        2.思考递归树的每一个状态（for循环条件）
        3.思考递归树的变量有哪些（回溯函数的形参）
        4.思考递归树的叶子节点是什么（到哪结束return并保存什么）
        '''
        def helper(nums:list,his:list):
            if len(nums)==0:
                self.ret.append(his)
                return
            for idx in range(len(nums)):
                if idx!=0 and nums[idx]==nums[idx-1]:   # 去重小技巧
                    continue
                helper(nums[:idx]+nums[idx+1:],his+[nums[idx]])
        nums.sort()
        helper(nums,[])
        return self.ret