public class Solution {
    public IList<IList<int>> Permute(int[] nums)
        {
            IList<IList<int>> result = new List<IList<int>>();
            permute(result, nums, 0);
            return result;
        }

        private void permute(IList<IList<int>> result, int[] array, int start)
        {
            if (start >= array.Length)
            {
                List<int> current = new List<int>();
                foreach (int a in array)
                {
                    current.Add(a);
                }
                result.Add(current);
            }
            else
            {
                for (int i = start; i < array.Length; i++)
                {
                    swap(array, start, i);
                    permute(result, array, start + 1);
                    swap(array, start, i);
                }
            }
        }

        private void swap(int[] array, int i, int j)
        {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
}