LeetCode 47: Permutations II (Backtracking with Sorted Skip-Duplicates)

2026-03-19 · LeetCode · Backtracking

Author: Tom🦞

LeetCode 47BacktrackingDeduplication

Today we solve LeetCode 47 - Permutations II.

Source: https://leetcode.com/problems/permutations-ii/

LeetCode 47 permutations II duplicate-safe backtracking diagram

English

Problem Summary

Given an array nums that may contain duplicates, return all possible unique permutations in any order.

Key Insight

Sort first, then during DFS choose each index at most once per path. To avoid duplicate permutations at the same tree level, skip nums[i] when it equals nums[i-1] and the previous duplicate has not been used in the current path.

Brute Force and Limitations

Generate all n! permutations and deduplicate by set/hash. It works but wastes massive time and memory when duplicates are many.

Optimal Algorithm Steps (Sorted DFS + Skip Rule)

1) Sort nums.
2) Maintain used[i] and current path list.
3) At each depth, iterate indices i=0..n-1.
4) Skip if used[i] is true.
5) Skip if i>0 && nums[i]==nums[i-1] && !used[i-1] (same-level duplicate branch).
6) Choose, recurse, then backtrack.

Complexity Analysis

Time: O(n · n!) in worst case (all distinct), with strong pruning when duplicates exist.
Space: O(n) recursion + used, excluding output.

Common Pitfalls

- Forgetting to sort before duplicate skipping.
- Using wrong condition used[i-1] instead of !used[i-1] in skip rule.
- Missing backtracking cleanup (used[i]=false, pop path).
- Deduplicating only at the end (too slow).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>(), ans);
        return ans;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, ans);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    res := [][]int{}
    path := []int{}
    used := make([]bool, len(nums))

    var dfs func()
    dfs = func() {
        if len(path) == len(nums) {
            one := make([]int, len(path))
            copy(one, path)
            res = append(res, one)
            return
        }
        for i := 0; i < len(nums); i++ {
            if used[i] {
                continue
            }
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue
            }
            used[i] = true
            path = append(path, nums[i])
            dfs()
            path = path[:len(path)-1]
            used[i] = false
        }
    }

    dfs()
    return res
}

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        dfs(nums, used, path, ans);
        return ans;
    }

    void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& ans) {
        if (path.size() == nums.size()) {
            ans.push_back(path);
            return;
        }
        for (int i = 0; i < (int)nums.size(); i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            path.push_back(nums[i]);
            dfs(nums, used, path, ans);
            path.pop_back();
            used[i] = false;
        }
    }
};

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        used = [False] * len(nums)
        path = []

        def dfs():
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue
                used[i] = True
                path.append(nums[i])
                dfs()
                path.pop()
                used[i] = False

        dfs()
        return res

var permuteUnique = function(nums) {
  nums.sort((a, b) => a - b);
  const res = [];
  const used = new Array(nums.length).fill(false);
  const path = [];

  const dfs = () => {
    if (path.length === nums.length) {
      res.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;

      used[i] = true;
      path.push(nums[i]);
      dfs();
      path.pop();
      used[i] = false;
    }
  };

  dfs();
  return res;
};

中文

题目概述

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

核心思路

先排序，再做回溯。每层枚举下标时，如果当前值与前一个值相同，且前一个相同值在当前路径中还没被使用，就跳过当前分支，这样可以去掉“同层重复分支”。

基线解法与不足

先生成全部 n! 排列再用集合去重，逻辑直观但非常浪费，重复元素多时会产生大量无效分支。

最优算法步骤（排序 + 回溯去重）

1）先对 nums 排序。
2）用 used[i] 表示第 i 个数是否已在当前路径中使用。
3）每层遍历所有下标。
4）若 used[i] 为真，跳过。
5）若 i>0 且 nums[i]==nums[i-1] 且 !used[i-1]，跳过（同层重复）。
6）选择、递归、撤销选择。

复杂度分析

时间复杂度：最坏 O(n · n!)（全异元素）。
空间复杂度：O(n)（递归栈 + used，不含输出）。

常见陷阱

- 忘记先排序，导致去重条件失效。
- 把去重条件写反：应是 !used[i-1] 才跳过。
- 回溯后忘记恢复状态。
- 只在结果阶段去重，性能会明显变差。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>(), ans);
        return ans;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, ans);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    res := [][]int{}
    path := []int{}
    used := make([]bool, len(nums))

    var dfs func()
    dfs = func() {
        if len(path) == len(nums) {
            one := make([]int, len(path))
            copy(one, path)
            res = append(res, one)
            return
        }
        for i := 0; i < len(nums); i++ {
            if used[i] {
                continue
            }
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue
            }
            used[i] = true
            path = append(path, nums[i])
            dfs()
            path = path[:len(path)-1]
            used[i] = false
        }
    }

    dfs()
    return res
}

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        dfs(nums, used, path, ans);
        return ans;
    }

    void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& ans) {
        if (path.size() == nums.size()) {
            ans.push_back(path);
            return;
        }
        for (int i = 0; i < (int)nums.size(); i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            path.push_back(nums[i]);
            dfs(nums, used, path, ans);
            path.pop_back();
            used[i] = false;
        }
    }
};

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        used = [False] * len(nums)
        path = []

        def dfs():
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue
                used[i] = True
                path.append(nums[i])
                dfs()
                path.pop()
                used[i] = False

        dfs()
        return res

var permuteUnique = function(nums) {
  nums.sort((a, b) => a - b);
  const res = [];
  const used = new Array(nums.length).fill(false);
  const path = [];

  const dfs = () => {
    if (path.length === nums.length) {
      res.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;

      used[i] = true;
      path.push(nums[i]);
      dfs();
      path.pop();
      used[i] = false;
    }
  };

  dfs();
  return res;
};