Leetcode47全排列II(回溯+剪枝)

简介: Leetcode47全排列II(回溯+剪枝)

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    let res = []
    function dfs(arr,rest){
    console.log(arr,rest)
        if(arr.length === nums.length){
            res.push(arr)
            return
        }

        for(let i=0;i<rest.length;i++){
            if(rest.indexOf(rest[i]) !== i){
                continue
            }else{
                arr.push(rest[i])
                let newRest = [...rest]
                newRest.splice(i,1)
                dfs([...arr],newRest)
                arr.pop()
            }
        }
    }
    dfs([],nums)
    return res
}

这道题还是思考了挺久的,看着一些解答方法的代码片段觉得不是那么很好理解。有的还要排序啊很麻烦觉着。
没想到晚上吃完饭回来竟然理解了一些
回溯都知道,重点是要去重
对于字符串的话去重简单一些
但是对于这道题,每一项里面也是一个字符串,还是剪枝比较好。
既然剪枝的逻辑在于剩余可选项中是否有重复项,那直接将有重复项的跳过不就行了?
举个简单实例
const nums = [1,1,2,2]
我们执行上述代码,打印结果如下

[] [ 1, 1, 2, 2 ]
[ 1 ] [ 1, 2, 2 ]
[ 1, 1 ] [ 2, 2 ]
[ 1, 1, 2 ] [ 2 ]
[ 1, 1, 2, 2 ] []
[ 1, 2 ] [ 1, 2 ]
[ 1, 2, 1 ] [ 2 ]
[ 1, 2, 1, 2 ] []
[ 1, 2, 2 ] [ 1 ]
[ 1, 2, 2, 1 ] []

也就是说,rest中如果有相同的元素,我直接过滤掉,不用再塞进去了,感兴趣的可以打印一下对比效果。因为太长我就不展示了

相关文章
|
2月前
|
决策智能
【LeetCode 50】77.组合(优化、剪枝操作)
【LeetCode 50】77.组合(优化、剪枝操作)
18 2
|
2月前
|
算法
Leetcode第46题(全排列)
这篇文章介绍了LeetCode第46题“全排列”的解题方法,使用深度优先搜索(DFS)和回溯算法来生成给定数组的所有可能排列。
31 0
Leetcode第46题(全排列)
|
2月前
Leetcode第47题(全排列II)
LeetCode第47题要求返回一个包含重复数字序列的所有不重复全排列,通过深度优先搜索和去重策略来解决。
32 0
|
4月前
|
算法
LeetCode第46题全排列
LeetCode第46题"全排列"的解题方法,利用回溯法避免重复并确保元素的有序性,生成所有可能的排列组合。
LeetCode第46题全排列
|
4月前
|
算法
LeetCode第47题全排列II
LeetCode第47题"全排列II"的解题方法,通过排序和添加去重逻辑,使用回溯法避免生成重复的排列组合。
|
4月前
|
Python
【Leetcode刷题Python】46. 全排列
本文介绍了LeetCode题目46的Python编程解决方案,题目要求给定一个不含重复数字的数组,返回该数组所有可能的全排列。
27 0
|
6月前
|
机器学习/深度学习 存储 算法
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
|
6月前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独