Permutations

Solution.cs

using System.Collections.Generic;

public class Solution {
  public IList<IList<int>> Permute(int[] nums) {
    
    IList<IList<int>> solution = new List<IList<int>>();
    Traverse(nums, new HashSet<int>(), new List<int>(), solution);
    return solution;
  }
  
  private void Traverse(int[] nums, HashSet<int> currentSet, List<int> currentList, IList<IList<int>> solution)
  {
    if(currentSet.Count == nums.Length)
    {
      solution.Add(new List<int>(currentList));
      return;
    }
    
    foreach(var num in nums)
    {
      if(currentSet.Add(num))
      {
        currentList.Add(num);
        Traverse(nums, currentSet, currentList, solution);
        if(currentSet.Count > 0)
        {
          currentSet.Remove(num);
          currentList.RemoveAt(currentList.Count - 1);
        }
      }
    }
  }
  
  
}