一次一粒沙，一次一件事。 ——《人性的优点》

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 中的所有整数 互不相同

思路：（回溯：暴力遍历）

回溯万能模板：

void backtracking(/* 所需参数（访问标记, 中间存储, 最终存储, 原始数据）*/) {// TODO 自动生成的方法存根if(/*终止条件*/) {//一种情况，加入最终存储return; //返回}for(/*对现有条件进行罗列*/) {if(/*判断是否合理，或者是否已访问*/) {continue;//跳过}//将该元素加入中间存储（修改条件）//标位已访问backtracking(/*参数*/); //递归调用自身//将该元素从中间存储删除（条件复位，即 ：回溯）//标记为未访问}}

本题注意点：ArrayList是一个引用类型，因此每次都要new一个再加入到list中

代码： (Java)

import java.util.ArrayList;
import java.util.List;public class arrangement {public static void main(String[] args) {// TODO 自动生成的方法存根int [] nums = {1, 2, 3};System.out.println(permute(nums));}public static List> permute(int[] nums) {List> alarr = new ArrayList<>();List midarr = new ArrayList<>();boolean [] hasVisited = new boolean [nums.length];if(nums == null || nums.length == 0) {return alarr;}backtracking(hasVisited, midarr, alarr, nums);return alarr;}private static void backtracking(boolean[] hasVisited, List midarr, List> alarr, int[] nums) {// TODO 自动生成的方法存根if(midarr.size() == hasVisited.length) {alarr.add(new ArrayList<>(midarr));//重新构造一个 Listreturn;}int n = hasVisited.length;for(int i = 0; i < n; i++) {if(hasVisited[i]) {continue;}midarr.add(nums[i]);hasVisited[i] = true;backtracking(hasVisited, midarr, alarr, nums);midarr.remove(midarr.size() - 1);hasVisited[i] = false;}}
}

运行结果：

其他同等解法的题目：

257. 二叉树的所有路径
79. 单词搜索
93. 复原 IP 地址
17. 电话号码的字母组合

注：仅供学习参考！

题目来源：力扣