全排列（算法） | 脑瓜呆呆

题目：

给定一个不含重复数字的数组 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]]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/permutations

代码：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

//n:小链表长度
//output:链表
//res:返回的链表
//frist: 表示从左往右填到第first 个位置
    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了，将列表放到结果集中
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            // Collections.swap()交换集合中两个位置的元素
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 撤销交换
            Collections.swap(output, first, i);
        }
    }
}

思路：

采用回溯法，从左往右每一个位置都依此尝试填入一个数，看能不能填完这 n个空格。

如果first=n，代表已经填完n个数，将队列放到结果集中。否则，填入一个之前没有填入过的数，使i=first，在first后的数字都没有填入过队列中，所以遍历first以后的数字，将数字填入first位置上，填完继续填下一位置。将全部的位置填完后，回到上一次递归的位置，将交换的两个数交换回来，即i与first位置上的数，继续for循环，一直到最后，全部的可能都排列出来。