Sharing my C# solution Recursive and DFS with comments


  • 0
    Y
    //Recursive solution
    // if current index is 0 return new List<IList<int>>(){new List<int>(){nums[0]}};
    // else
    // get the index - 1 list, 
    // go through all the list in index - 1 lists, colone index -1 times for each of the list from index - 1 
    // insert nums[index] into from 0 to index - 1 position of all the coloned lists.
    // add nums[index] to last of the index - 1 lists.
    
    
    public class Solution {
        public IList<IList<int>> Permute(int[] nums) {
            
            return Permute(nums,nums.Length-1);
            
        }
        
        public IList<IList<int>> Permute(int[] nums, int index) {
            
            if(index==0)
                return new List<IList<int>>(){new List<int>(){nums[0]}};
            
            var result=new List<IList<int>>();
            
            var pre = Permute(nums, index - 1);
            
            foreach(var item in pre)
            {
                for(int i = 0 ; i < index; i++)
                {
                    var newList=new List<int>();
                    
                    foreach(var number in item)
                    {
                        newList.Add(number);
                    }                    
                    newList.Insert(i,nums[index]);
                    result.Add(newList);
                }
                
                item.Add(nums[index]);
                
                result.Add(item);
            }
            
            return result;  
        }
    }
    
    //DFS solution:
    // consider DFS in a n*n(nums.Length) arrays, every layer take one number.
    
    public class Solution {
        public IList<IList<int>> Permute(int[] nums) {
            //DFS way
            var result=new List<IList<int>>();
            DFS(nums,result,new List<int>());
                return result;
        }
        
        
        public void DFS(int[]nums, IList<IList<int>> result, IList<int> curr)
        {
            if(curr.Count==nums.Length)
            {
                result.Add(curr);
                return;
            }
                
            for(int i=0; i<nums.Length; i++)
            {
                if(!curr.Contains(nums[i]))
                {
                    //colone list
                    var newList=new List<int>();
                    foreach(var item in curr)
                    {
                        newList.Add(item);
                    }
                    newList.Add(nums[i]);
                    DFS(nums, result, newList);
                }
            }
        }
    }

  • 0
    R

    public void NextPermutation(int[] nums) {
    if (nums == null || nums.Length < 2)
    {
    return;
    }

        //1) scan from back to front and find out the pivotal index
        //pivot is the index of an element which is greater than its previous one
        //2. scran from the pivot to the end of array to reverse order while switch the position of 
        //pivot-1 element with the one within its value range, i.e. 2,4,3,1,  will need to swap 2 with 3, then it is 3,4,2,1, 
        //after reverse, finally it becomes 3,1,2,4
        
        int val = int.MaxValue;
        int pivot = nums.Length -1;
        while (pivot > 0)
        {
            if (nums[pivot] > nums[pivot-1])
            {
                int i = pivot;
                val = nums[pivot-1];
                int k = nums.Length -1;
                
                int replaceIndex = -1;
                    
                while (i <= k)
                {
                    if (replaceIndex < 0)
                    {
                        //from pivot to end and look for swap position
                        if (i == k || val < nums[i] && val >= nums[i+1])
                        {
                            replaceIndex =  i;
                        }
                        else if (val >= nums[k] && val < nums[k-1])
                        {//from end to pivot and look for swap position
                            replaceIndex =  k-1;
                        }
                        else if(val < nums[k])
                        {//if val is smaller than any element from pivot to end, swap with the end
                            replaceIndex =  k;
                        }
                        
                        if (replaceIndex > 0)
                        {
                            nums[pivot -1] = nums[replaceIndex];
                            nums[replaceIndex] = val;
                        }
                    }
                    
                    //reverse
                    if (i == k) break;
                    
                    int temp = nums[k];
                    nums[k] = nums[i];
                    nums[i] = temp;
                
                    i++;
                    k--;
                }
                
                break;
            }
            
            pivot--;
        }
        
        //sort
        if (val == int.MaxValue) Array.Sort(nums);
    }

Log in to reply
 

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