题目

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

解析

“全排列”就是一个非常经典的“回溯”算法的应用。我们知道，N 个数字的全排列一共有 N! 这么多个。
大家可以尝试一下在纸上写 3 个数字、4 个数字、5 个数字的全排列，相信不难找到这样的方法。
以数组 [1, 2, 3] 的全排列为例。

我们先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]；
再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]；
最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]。

我们只需要按顺序枚举每一位可能出现的情况，已经选择的数字在接下来要确定的数字中不能出现。按照这种策略选取就能够做到不重不漏，把可能的全排列都枚举出来。

在枚举第一位的时候，有 3 种情况。
在枚举第二位的时候，前面已经出现过的数字就不能再被选取了；
在枚举第三位的时候，前面 2 个已经选择过的数字就不能再被选取了。

这样的思路，我们可以用一个树形结构表示。看到这里的朋友，建议自己先尝试画一下“全排列”问题的树形结构。
使用编程的方法得到全排列，就是在这样的一个树形结构中进行编程，具体来说，就是执行一次深度优先遍历，从树的根结点到叶子结点形成的路径就是一个全排列。

树形结构图

代码

     public IList<IList<int>> Permute(int[] nums) {
        IList<IList<int>> res = new List<IList<int>>();
        int[] tempArr = new int[nums.Length];
        bool[] vis = new bool[nums.Length];
        BackTrackPermute(0,nums.Length,nums,vis,res,tempArr);
        return res;
    }

    void BackTrackPermute(int cur,int len,int[] nums, bool[] vis,IList<IList<int>> res,int[] tempArr)
    {
        if (cur == len)
        {
            res.Add(new List<int>(tempArr));
            return;
        }

        for (int i = 0; i < len; i++)
        {
            if(vis[i]) continue;//如果已经使用则继续
            vis[i] = true;
            tempArr[cur] = nums[i];//把当前的cur的值赋为nums[i]的值
            BackTrackPermute(cur+1,len,nums,vis,res,tempArr);//继续
            vis[i] = false; //状态重置
        }
    }