46. 全排列(中等)

1，问题描述

46. 全排列

难度：中等

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

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

2，初步思考

​ 直接看了官方的题解，是回溯的方法

​ 他们的题解中比较巧妙的一点是将数组进行了切分，以及使用过的（左），还未使用过的（右）

3，代码处理

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class _46全排列 {

    // 解法：回溯，比较巧妙的是进行数组切分成左右，左已经处理过，右还未处理
    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> output = new ArrayList<>();
        for (int num : nums) {
            output.add(num);
        }
        backtrack(len, 0, output, res);
        return res;
    }

    private void backtrack(int len, int index, List<Integer> output, List<List<Integer>> res) {
        if (index == len) res.add(new ArrayList<>(output));
        for (int i = index; i < len; i++) {
            Collections.swap(output, index, i);// 交换位置，递归处理
            backtrack(len, index + 1, output, res);
            Collections.swap(output, index, i);// 恢复原样
        }
    }
}