LeetCode LCR 084. 全排列 II

Categories:

题目描述
思路分析
1. 解法一：排序 + 回溯剪枝（推荐）
相似题目

题目描述

✅ LCR 084. 全排列 II

思路分析

解法一：排序 + 回溯剪枝（推荐）

核心思路：

先对数组排序，保证重复元素相邻。

回溯时用 used 记录元素是否已使用。

若当前元素与前一个相同且前一个未使用，跳过以避免重复排列。

复杂度分析：

时间复杂度：O(n * n!)，其中 n 表示元素个数。

空间复杂度：O(n)，用于递归栈与标记数组。

import java.util.*;

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

    private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.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, res);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

import "sort"

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

	var dfs func()
	dfs = func() {
		if len(path) == len(nums) {
			tmp := make([]int, len(path))
			copy(tmp, path)
			res = append(res, tmp)
			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
}

相似题目

题目	难度	考察点
46. 全排列	中等	回溯
39. 组合总和	中等	回溯
40. 组合总和 II	中等	回溯
78. 子集	中等	回溯
90. 子集 II	中等	回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/96904022