全排列II

难度：中等

题目描述

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

题解

用 $n$ 表示数组 $nums$ 的长度，创建列表 $temp$ 用于存储当前排列，生成排列的做法是将数组 $nums$ 中的每个元素按照特定顺序依次加入 $temp$，当 $temp$ 中的元素个数等于 $n$ 时，即可得到一个排列

在排列后的数组 $nums$ 中遍历到下标 $i$ 时，一下两种情况不应将 $nums[i]$ 加入当前排列

• 如果 $nums[i]$ 已经加入当前数列，则不能多次加入当前排列
• 如果当 $i>0$ 时，$nums[i]=nums[i-1]$ 且 $nums[i-1]$ 未加入当前数列，则不能将 $nums[i]$ 加入当前数列

其余情况下，执行如下操作

• 将 $nums[i]$ 加入当前排列，并将该元素的状态更新为已经加入当前排列，然后继续回溯
• 将当前排列末尾元素（即 $nums[i]$ ）移除，并将该元素的状态更新为未加入当前排列，恢复到原始状态

遍历结束之后，即可得到数组 $nums$ 的无重复全排列

想法代码

public class Solution
{
    IList<IList<int>> permutations = new List<IList<int>>();
    IList<int> temp = new List<int>();
    int[] nums;
    int n;
    bool[] visited;

    public static void Main(string[] args)
    {
        int[] nums = { 1, 1, 2 };
        Solution solution = new Solution();
        IList<IList<int>> res = solution.PermuteUnique(nums);
        foreach (var a in res)
        {
            foreach (var b in a)
            {
                Console.Write(b + " ");
            }
            Console.WriteLine();
        }
    }

    public IList<IList<int>> PermuteUnique(int[] nums)
    {
        Array.Sort(nums);
        this.nums = nums;
        this.n = nums.Length;
        this.visited = new bool[n];
        Backtrack(0);
        return permutations;
    }

    public void Backtrack(int index)
    {
        if (index == n)
        {
            permutations.Add(new List<int>(temp));
        }
        else
        {
            for (int i = 0; i < n; i++)
            {
                if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]))
                {
                    continue;
                }
                temp.Add(nums[i]);
                visited[i] = true;
                Backtrack(index + 1);
                temp.RemoveAt(index);
                visited[i] = false;
            }
        }
    }
}