# Sharing my C# solution Recursive and DFS with comments

• ``````//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.Insert(i,nums[index]);
}

}

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)
{
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)
{
}
DFS(nums, result, newList);
}
}
}
}``````

• 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);
}``````

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