public class Solution {

    public IList<IList<int>> Permute(int[] values)
    {
        return Perm(values);
    }

    public IList<IList<int>> Perm(int[] values)
    {
        if (values.Length == 1)
            return new List<IList<int>>(new[] { values });

        else
        {
            return values
                .SelectMany((value, index) =>
                {
                    var primary = new[] { value };
                    return this.Perm(Splice(values, index))
                        .Select(perm =>
                        {
                            return primary.Concat(perm).ToList() as IList<int>;
                        });
                })
                .ToList();
        }
    }

    public int[] Splice(int[] list, int index)
    {
        if (index >= list.Length)
            throw new Exception();

        else return list
            .Take(index)
            .Concat(list.Skip(index + 1))
            .ToArray();
    }
}