C# DFS solution sharing


  • 0
    Y

    //DFS

    public class Solution {
    public IList<IList<int>> PermuteUnique(int[] nums) {

        Array.Sort(nums);
        
        var result = new List<IList<int>>();
        
        DFS(nums,result,new Dictionary<int,int>());
        
        return result;
        
    }
    
    public void DFS(int[]nums, IList<IList<int>> result, Dictionary<int,int> curr)
    {
        if(curr.Count == nums.Length)
        {
            result.Add(curr.Values.ToList());
            return;
        }
            
        for(int i = 0; i < nums.Length; i++)
        {
            if(!curr.ContainsKey(i))
            {
                //colone list
                var newList = new Dictionary<int,int>();
                foreach(var item in curr)
                {
                    newList.Add(item.Key,item.Value);
                }
                newList.Add(i,nums[i]);
                DFS(nums, result, newList);
                
                while(i<nums.Length-1 && nums[i+1]==nums[i])
                {
                    i += 1;
                }
            }
        }
    }
    }

Log in to reply
 

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