LeetCode 47、全排列II

一、题目描述

给定一个可包含重复数字的序列 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]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
   public List<List<Integer>> permuteUnique(int[] nums) {

        // 排序（升序或者降序都可以），排序是剪枝的前提
        Arrays.sort(nums);

        // 结果集合
        List<List<Integer>> sets = new ArrayList<List<Integer>>();

        // 每次的子集
        List<Integer> path = new ArrayList<Integer>();


        Boolean[] used = new Boolean[nums.length];

        // 每个元素默认一开始都没有被选择
        Arrays.fill(used, false);

        // 执行回溯算法
        backtrack( nums , path,used , sets);

        // 返回结果
        return sets;

    }

    // used 表示递归时正在访问的数组元素是否之前已经被访问过
    // nums 表示当前集合中的元素
    // path 表示每次递归后生成的子集
    // sets 表示最终生成的所有子集合
    private void backtrack(  int[] nums , List<Integer> path , Boolean[] used , List<List<Integer>> sets ){

        // 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
        if( path.size() == nums.length){
            // 每次确定好一个子集，都把它加入到结果集合中
            sets.add(new ArrayList<Integer>(path));
            return;
        }

        for( int i = 0 ; i < nums.length ; i++ ){

            if(!used[i]){

                if( i > 0 && nums[i] == nums[i - 1] && used[i-1]){
                    continue;
                }
                // 把本次递归访问的元素加入到 subset 数组中
                path.add(nums[i]);

                used[i] = true;

                // 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
                // 本题不需要剪枝
                // 5、做出选择，递归调用该函数，进入下一层继续搜索
                // 递归
                backtrack( nums , path ,used, sets);

                // 6、撤销选择，回到上一层的状态
                // 取消对 nums[i] 的选择
                used[i] = false;
                path.remove(path.size() - 1);

            }
            
        }

    }
}

Python

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """
        :param nums: List[int]
        :return: List[List[int]]
        """
        # 排序（升序或者降序都可以），排序是剪枝的前提
        nums.sort()

        # 结果集合
        sets = []

        # 每次的子集
        path = []

        used = [False] * len(nums)

        # 执行回溯算法
        self.backtrack(nums, path, used, sets)

        # 返回结果
        return sets

    def backtrack(self, nums, path, used, sets):
        """
        :param nums: List[int]
        :param path: List[int]
        :param used: List[bool]
        :param sets: List[List[int]]
        """
        # 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
        if len(path) == len(nums):
            # 每次确定好一个子集，都把它加入到结果集合中
            sets.append(path[:])
            return

        for i in range(len(nums)):
            if not used[i]:
                if i > 0 and nums[i] == nums[i - 1] and  used[i - 1]:
                    continue
                # 把本次递归访问的元素加入到 subset 数组中
                path.append(nums[i])

                used[i] = True

                # 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
                # 本题不需要剪枝
                # 5、做出选择，递归调用该函数，进入下一层继续搜索
                # 递归
                self.backtrack(nums, path, used, sets)

                # 6、撤销选择，回到上一层的状态
                # 取消对 nums[i] 的选择
                used[i] = False
                path.pop()