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

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

```javascript

/**

* @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]

我们执行上述代码，打印结果如下

```javascript

[] [ 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中如果有相同的元素，我直接过滤掉，不用再塞进去了，感兴趣的可以打印一下对比效果。因为太长我就不展示了