47. 全排列 II

中等回溯排序 + 回溯（used 剪枝重复）力扣原题 ↗

题目描述

输入一个整数数组 nums，其中可能有相同的数。

把全部元素各用一次排成一个序列，就是一个排列。返回所有互不相同的排列：由于交换两个相同的数而得到的同一序列只能出现一次。返回顺序不限。

示例 1

输入：nums = [1,1,2]
输出：[[1,1,2],[1,2,1],[2,1,1]]

解释：两个 1 互换不产生新序列，只有 3 种不同的排列。

示例 2

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

解释：没有重复元素，共 6 种排列。

数据范围

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

解题思路：排序 + 回溯（used 剪枝重复）

先排序让相同的数相邻，再用 used 数组逐位填排列。关键是去重规则：如果 nums[i] 与 nums[i-1] 相同且 nums[i-1] 还没被用，就跳过 nums[i]。这等于规定一组相同的数必须按下标从小到大的顺序使用，于是每种数值排列只会被生成一次。

为什么正确

任何时刻，每组相同数字中被使用的都是下标最小的若干个，且按下标顺序进入 path。

复杂度分析

时间 O(n · n!)，空间 O(n)（不计输出）。

易错点

忘记先排序，或者把条件写成 used[i-1]（反向）却不理解其含义；未排序时相同的数不相邻，去重条件完全失效。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

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

        def dfs():
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if used[i] or (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

class Solution {
    int[] nums;
    boolean[] used;
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        used = new boolean[nums.length];
        dfs();
        return res;
    }

    void dfs() {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            dfs();
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        function<void()> dfs = [&]() {
            if (path.size() == nums.size()) {
                res.push_back(path);
                return;
            }
            for (int i = 0; i < (int)nums.size(); i++) {
                if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                    continue;
                }
                used[i] = true;
                path.push_back(nums[i]);
                dfs();
                path.pop_back();
                used[i] = false;
            }
        };
        dfs();
        return res;
    }
};

func permuteUnique(nums []int) [][]int {
	sort.Ints(nums)
	res, path := [][]int{}, []int{}
	used := make([]bool, len(nums))
	var dfs func()
	dfs = func() {
		if len(path) == len(nums) {
			res = append(res, append([]int{}, path...))
			return
		}
		for i := 0; i < len(nums); i++ {
			if used[i] || (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
}

var permuteUnique = function(nums) {
    nums.sort((a, b) => a - b);
    const res = [], path = [];
    const used = new Array(nums.length).fill(false);
    const dfs = () => {
        if (path.length === nums.length) {
            res.push([...path]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i] || (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;
};

function permuteUnique(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const res: number[][] = [], path: number[] = [];
    const used = new Array(nums.length).fill(false);
    const dfs = (): void => {
        if (path.length === nums.length) {
            res.push([...path]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i] || (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;
}

载入编辑器，自己跑一遍 →

其他解法

回溯法通过“相同元素必须按顺序使用”的剪枝来去重，框架可推广到带约束的搜索；下一个排列法按字典序逐个枚举不同排列，去重由严格比较自然保证，额外空间为常数。

解法 2：反复求下一个排列时间 O(n·n!)，空间 O(1)

先把数组升序排列，这是字典序最小的排列。之后反复执行第 31 题“下一个排列”：从右往左找第一个 nums[i] < nums[i+1] 的位置 i；再从右往左找第一个大于 nums[i] 的 nums[j]，交换两者；最后把 i 右侧反转成升序。每得到一个新排列就记录下来，直到找不到 i（已是降序，即最大排列）为止。比较时用严格大小关系，所以相等元素不会生成重复排列。

不需要递归和 used 数组，除结果外只占常数空间，并且天然按字典序、自动去重。缺点是要先掌握“下一个排列”的推导，而且无法像回溯那样在中途加入剪枝条件。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = [nums[:]]
        while True:
            i = n - 2
            while i >= 0 and nums[i] >= nums[i + 1]:
                i -= 1
            if i < 0:
                break
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
            nums[i + 1:] = nums[i + 1:][::-1]
            res.append(nums[:])
        return res

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        while (true) {
            List<Integer> p = new ArrayList<>();
            for (int x : nums) p.add(x);
            res.add(p);
            int i = n - 2;
            while (i >= 0 && nums[i] >= nums[i + 1]) i--;
            if (i < 0) break;
            int j = n - 1;
            while (nums[j] <= nums[i]) j--;
            int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
            for (int l = i + 1, r = n - 1; l < r; l++, r--) {
                t = nums[l]; nums[l] = nums[r]; nums[r] = t;
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> res{nums};
        while (true) {
            int i = n - 2;
            while (i >= 0 && nums[i] >= nums[i + 1]) i--;
            if (i < 0) break;
            int j = n - 1;
            while (nums[j] <= nums[i]) j--;
            swap(nums[i], nums[j]);
            reverse(nums.begin() + i + 1, nums.end());
            res.push_back(nums);
        }
        return res;
    }
};

func permuteUnique(nums []int) [][]int {
	sort.Ints(nums)
	n := len(nums)
	res := [][]int{}
	for {
		res = append(res, append([]int{}, nums...))
		i := n - 2
		for i >= 0 && nums[i] >= nums[i+1] {
			i--
		}
		if i < 0 {
			break
		}
		j := n - 1
		for nums[j] <= nums[i] {
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
		for l, r := i+1, n-1; l < r; l, r = l+1, r-1 {
			nums[l], nums[r] = nums[r], nums[l]
		}
	}
	return res
}

var permuteUnique = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length, res = [];
    while (true) {
        res.push([...nums]);
        let i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i < 0) break;
        let j = n - 1;
        while (nums[j] <= nums[i]) j--;
        [nums[i], nums[j]] = [nums[j], nums[i]];
        for (let l = i + 1, r = n - 1; l < r; l++, r--) [nums[l], nums[r]] = [nums[r], nums[l]];
    }
    return res;
};

function permuteUnique(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const n = nums.length, res: number[][] = [];
    while (true) {
        res.push([...nums]);
        let i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i < 0) break;
        let j = n - 1;
        while (nums[j] <= nums[i]) j--;
        [nums[i], nums[j]] = [nums[j], nums[i]];
        for (let l = i + 1, r = n - 1; l < r; l++, r--) [nums[l], nums[r]] = [nums[r], nums[l]];
    }
    return res;
}

回溯专题的其他题目

查看回溯全部题目 →