Given a list of numbers, return all possible permutations.

Notice

You can assume that there is no duplicate numbers in the list.

Have you met this question in a real interview?

Yes

Example

For nums =[1,2,3], the permutations are:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Challenge

Do it without recursion.

Solution1: https://leetcode.com/problems/permutations/description/

public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        IList<IList<int>> result =new List<IList<int>>();

        DFS(nums,0,result);
        return result;        
    }
    public void DFS(int[] nums,int offset,IList<IList<int>> result) {

        if (offset == nums.Length){
            result.Add(new List<int>(nums));
        }
        List<int> subset = new List<int>();
        for (int i = offset; i < nums.Length; i++)
        {
            if (subset.Contains(nums[i])){
              // skip if we already done swap with this item
                continue;
            } 

            subset.Add(nums[i]);

            Swap(nums, offset, i);
            DFS(nums, offset + 1,result);
            Swap(nums, offset, i);
        }

    }
    private static void Swap(int[] nums, int index1, int index2)
    {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}