☆打卡算法☆LeetCode 47、全排列II 算法解析

示例 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]]

public class Solution {
    public IList<IList<int>> PermuteUnique(int[] nums) {
        //DFS
        Queue<List<int>> container = new Queue<List<int>>();
        Queue<List<int>> usedIndex = new Queue<List<int>>();

        container.Enqueue(new List<int>());
        usedIndex.Enqueue(new List<int>());
        Array.Sort(nums);

        //一共需要执行的层数
        for(int layer=0;layer<nums.Length;layer++){
            //记录容器当前层的数据个数
            int cnt = container.Count;
            for(int i=0;i<cnt;i++){
                var data = container.Dequeue();
                var used = usedIndex.Dequeue();
                int lastUse = -11;
                for(int j=0;j<nums.Length;j++){
                    //查找当前数字是否使用过
                    if(!used.Contains(j) &amp;&amp; lastUse!=nums[j]){
                        //如果没有就复制前面层的所有数字并加入这个特殊数字
                        var temp = new List<int>(data);
                        var tempIndex = new List<int>(used);
                        temp.Add(nums[j]);
                        tempIndex.Add(j);
                        lastUse = nums[j];
                        container.Enqueue(temp);
                        usedIndex.Enqueue(tempIndex);
                    }
                }
            }
        }
        List<IList<int>> res = new List<IList<int>>(container);
        return res;
    }
}