C# - use bool array to track used, key to unique is initial sort


  • 0
    public IList<IList<int>> PermuteUnique(int[] nums) 
    {
        IList<IList<int>> lists = new List<IList<int>>();
        Array.Sort(nums);
        Permute(nums, new bool[nums.Length], new List<int>(), lists);
        return lists;
    }
    
    public void Permute(int[] nums, bool[] used, IList<int> curr, IList<IList<int>> lists)
    {
        if (curr.Count == nums.Length)
        {
            lists.Add(curr);
            return;
        }
        
        for (int i = 0; i < nums.Length; i++)
        {
            if (!used[i])
            {
                used[i] = true;
                IList<int> next = new List<int>(curr);
                next.Add(nums[i]);
                Permute(nums, used, next, lists);
                used[i] = false;
                
                int lastUsed = nums[i];
                
                // do not Permute same value twice in a row
                while (i < nums.Length - 1 && (used[i+1] || nums[i+1] == lastUsed))
                {
                    i++;
                }
            }
        }
    }

  • 0
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.