47. 全排列 II

[buuing]

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/permutations-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 回溯算法

这道题虽然不难, 但是作为全排列的进阶, 这里引入了一个在回溯算法中的优化技巧: 剪枝 在题目中出现了相同的数字, 那就增加一个哈希表来判断, 如果同一层级第二次出现了相同的数字, 那就剪掉

       [1, 1, 2]
   /       |      \
  1        -       2
 /  \             / \
1    2            1  -
|    |            |
2    1            1

const permuteUnique = nums => {
  if (!nums.length) return []
  let res = []
  const dfs = (map, arr) => {
    if (arr.length === nums.length) {
      return res.push(arr.slice())
    }
    let set = {}
    for (let i = 0; i < nums.length; i++) {
      let curr = nums[i]
      if (map[i] || set[curr]) continue
      set[curr] = 1
      map[i] = 1
      arr.push(curr)
      dfs(map, arr)
      arr.pop()
      map[i] = 0
    }
  }
  dfs([], [])
  return res
}