Simple C# solution with proper explanation

  • 0

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

    	Dictionary<int, IList<IList<int>>> dict = new Dictionary<int, IList<IList<int>>>(){};
    	// Permutation of just the first element; 
    	IList<IList<int>> listOne = new List<IList<int>>(){new List<int>(){nums[0]}};		
    	dict.Add(0, listOne);
    	// For every element, get the list of the previous element and just add the current number is all possible positions. That's it. Meaning the number will be in position-1 for all lists, then in position-2 for all the lists and so on.
    	for(int i=1; i<nums.Length; i++)			
    		dict.Add(i, ComputeCurrentPermutations(dict[i-1], nums[i], i+1));
    	return dict[nums.Length-1];
    // Get the list of the previous element and add current number in all possible positions;
    private IList<IList<int>> ComputeCurrentPermutations(IList<IList<int>> prevList, int currentNum, int currentPosition)
    	IList<IList<int>> currentPerm = new List<IList<int>>(){};
    	for(int i=0; i<currentPosition ; i++) 		// Loop through all possible positions of the new number
    		for(int j=0; j<prevList.Count(); j++)
    			IList<int> currentLine =  new List<int>(prevList[j]); // copy just the elements from previous list, not the reference, Doing this'd be by reference - "IList<int> currentLine =  prevList[j];"
    			currentLine.Insert(i, currentNum);
    	return currentPerm;			// #Win.


Log in to reply

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