全排列

难度：中等

题目描述

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例1

输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2

输入：nums = [0,1] 输出：[[0,1],[1,0]]

示例3

输入：nums = [1] 输出：[[1]]

题解

用 $n$ 表示数组 $nums$ 的长度，创建列表 $temp$ 用于存储当前排列，将数组 $nums$ 中每个元素依次加入 $temp$，然后根据 $temp$ 生成全排列

为了得到数组 $nums$ 的全排列，需要依次确定排列中的每个位置的元素，可以通过交换 $temp$ 中的元素实现，对于 $0\leq index<n$，按照下标 $index$ 从小到大的顺序依次确定每个 $temp[index]$ 的值，即能得到一个排列

• 当 $index=0$，可以将 $temp[0]$ 和任意一个元素交换（包括和自身交换），经过一次交换之后即可确定当前排列中的 $temp[0]$ 的值
• 当 $index>0$，如果当前排列中 $temp[0]$ 到 $temp[index-1]$ 的值都已经确定，则可以将 $temp[index]$ 和任意一个下标大于等于 $index$ 的元素交换，经过一次交换之后即可确定当前排列中 $temp[index]$ 的值

通过上述分析，可以利用回溯法，步骤如下：

• 如果 $index=n$，则当前排列中的所有元素都已经确定，则将当前排列添加到结果列表中
• 如果 $index<n$，则对于每一个 $index\leq i<n$，执行如下操作：
  • 将 $temp[index]$ 和 $temp[i]$ 的值交换，然后将 $index+1$ 作为当前下标继续搜索
  • 将 $temp[index]$ 和 $temp[i]$ 的值再次交换，恢复到交换之前的状态

当每个下标对应的所有可能的值都遍历结束之后，就可以得到数组 $nums$ 的全排列

想法代码

class Solution
{
    IList<IList<int>> permutations = new List<IList<int>>();
    IList<int> temp = new List<int>();
    int n;

    public static void Main(String[] args)
    {
        int[] nums = { 1, 2, 3 };
        Solution solution = new Solution();
        IList<IList<int>> res = solution.Permute(nums);
        foreach (var a in res)
        {
            foreach (var b in a)
            {
                Console.Write(b + " ");
            }
            Console.WriteLine();
        }
    }

    public IList<IList<int>> Permute(int[] nums)
    {
        foreach (int i in nums)
        {
            temp.Add(i);
        }
        n = nums.Length;
        BackTrack(0);
        return permutations;
    }

    public void BackTrack(int index)
    {
        if (index == n)
        {
            permutations.Add(new List<int>(temp));
        }
        else
        {
            for (int i = index; i < n; i++)
            {
                Swap(temp,index,i);
                BackTrack(index+1);
                Swap(temp, index, i);
            }
        }
    }

    public void Swap(IList<int> temp, int index1, int index2)
    {
        int cur = temp[index1];
        temp[index1] = temp[index2];
        temp[index2] = cur;
    }
}