二哥的 LeetCode 刷题笔记：全排列，回溯算法搞定

二哥逼逼：昨天熬夜看了 TI13，雪碧被 nous 干了个 0:2，直接掉到败者组，感觉好解气啊，就喜欢这种强队被弱队干掉的感觉，然后 XG 的胜者组就能少遇点强队。😄今天继续来学习 LeetCode 的第 46 题，全排列。

题意

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

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• 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]]

分析

题意非常朴素，让我们找出nums的所有排列组合。

那我们就可以用回溯算法来解决，遍历数组的每一个元素，然后尝试生成所有的排列，当生成一个完整的排列时，记录该排列，并退回到上一步，然后继续生成新的排列。

就比如说“123”，我们可以先固定 1，然后递归处理 “23”。把 “123”、“132” 排列完成后，回溯到上一步，固定 2，然后递归...