体会回溯的方法在求解排列问题中的应用，掌握使用数组记录每次走过的路的技巧，体会在这样的过程中状态重置的意义。这一节的标题更确切来说，应该叫“全排列”问题。
例题1：LeetCode 第 46 题：全排列
传送门：英文网址：46. Permutations ，中文网址：46. 全排列 。
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
分析：事实上，这是一个非常典型的使用回溯法来解决的问题。首先，我们可以很容易地要发现递归结构：
理解这张图：问题做到这个地方，我们感觉到递归算法有点类似与暴力解法一样，来帮助我们寻求问题的所有可能解。
我们看到，上图第 1 层的节点有 3 条路可以走，第 2 层的节点有 2 条路可以走，第 3 层只有 1 条路可以走，于是我们就找到了答案。
那么这样的过程我们应该如何描述呢？
我们不妨这样来理解？其实在每一层，我们都有 3 条路供我们选择，只不过这里是排序问题，之前已经走过的路，我们不能再走，这是题目给出的规则，那么我们从当前节点走到下一节点的时候，就要问一问自己，哪些路已经走过了，在生活中，我们做这样的问题，可以列一张表，走过一站在上面打一个勾，而在我们的代码实现中，就可以使用一个布尔型数组，来记录之前走过的路。
代码关键部分如下：
for (int i = 0; i < nums.length; i++) {
if (!used[i]) {
used[i] = true;
integers.add(nums[i]);
generatePermutation(nums, index + 1, integers);
used[i] = false;
integers.remove(integers.size() - 1);
}
}
这里的难点在于，体会为什么图中我们看到每一层往下的分支是越来越少，但是我们的递归函数每一层的 for 循环上限仍然是 nums.length , 这是因为我们使用了 used 数组记录了每一个递归层走过的路，只要之前走过了，这一层这条路就被“砍断”，这里“砍断”的意思就是“什么都不做”。在递归到底以后，需要一层一层回溯，所以状态要重置，所以代码结构看起来就是“对称的”。
- 从分析的过程可知，这是一个典型的树形问题；下一层问题与上一层的问题是同一个问题，只不过处理的数据不同；
- 递归回溯算法有点类似与暴力解法，来帮助我们搜索问题的所有的解，搜索的过程类似于深度优先遍历，是一个回溯搜索的过程（走到底的时候，回到上一层）；
- 对于排列问题的实现技巧：一旦我们使用了一个数字，就会影响下一步递归的范围。我们看到下一层处理的数据规模总是比上一层的少 1 ，直到叶子节点时只处理 1个数据，递归调用返回；因此我们可以使用一个 used 数组来记录走到叶子节点的时候使用了哪些数字，即递归向下的时候设置这些数字为“已经使用状态”，但是我们还要注意，回溯向上的时候，要将一层一层地将数字置为“未使用状态”，因此，整个递归回溯过程结束以后，就好像所有的数组都没有被使用过一样（事实上，我们在 debug 的时候，可以打印这
used数组，验证我们的想法）； - 在递归到底以后，需要一层一层回溯，所以状态要重置，所以代码结构看起来就是"对称的"；
- 画出递归结构图真的是我们发现递归关系的一个好方法，能画好树形结构的图，就可以尝试是否可以使用回溯方法解决。
Java 代码：
public class Solution {
private List<List<Integer>> result = new ArrayList<>();
private boolean[] used;
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0) {
return result;
}
int numsLen = nums.length;
used = new boolean[numsLen];
for (int i = 0; i < numsLen; i++) {
used[i] = false;
}
generatePermutation(nums, 0, new ArrayList<Integer>());
return result;
}
/**
* 树形问题使用回溯算法的一个套路是：在循环中使用递归。
* <p>
* integers 中保存了一个有 index-1 个元素的排列。
* 向这个排列的末尾添加第 index 个元素, 获得一个有 index 个元素的排列
*
* @param nums
* @param index
* @param integers
*/
private void generatePermutation(int[] nums, int index, ArrayList<Integer> integers) {
if (index == nums.length) {
// 这里有个坑，integers 是一个指针，所以要新建一个对象放进去
result.add(new ArrayList<>(integers));
return;
}
for (int i = 0; i < nums.length; i++) {
if (!used[i]) {
used[i] = true;
integers.add(nums[i]);
generatePermutation(nums, index + 1, integers);
used[i] = false;
integers.remove(integers.size() - 1);
}
}
}
public static void main(String[] args) {
Solution solution = new Solution();
List<List<Integer>> permute = solution.permute(new int[]{1, 2, 3, 4});
System.out.println(permute);
System.out.println(permute.size());
}
}
总结：使用一个数组进行状态的记录，也是我们在算法过程中常常使用到的技巧。这道题的解答具体一定代表性，希望认真体会其中用到的技巧。在递归层一层一层减少的时候，我们可以使用一个数组来记录已经走过的路的状态。在递归到底以后，需要一层一层回溯，所以状态要重置，所以代码结构看起来就是"对称的"。
这里的代码包括了打印 used 数组的输出的代码，提交到 LeetCode 的时候，应该删去。
Python 代码：
class Solution:
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) == 0:
return []
used = [False] * len(nums)
res = []
self.__dfs(nums, 0, [], used, res)
return res
def __dfs(self, nums, index, pre, used, res):
# 先写递归终止条件
if index == len(nums):
res.append(pre.copy())
return
for i in range(len(nums)):
if not used[i]:
# 如果没有用过，就用它
used[i] = True
pre.append(nums[i])
self.__dfs(nums, index + 1, pre, used, res)
used[i] = False
pre.pop()
练习1：LeetCode 第 47 题：全排列 II
传送门：英文网址：47. Permutations II ，中文网址：47. 全排列 II 。
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
求解关键：找到重复的原因，对树进行剪枝。
1、首先将数组排序，这一步很关键，是后面剪枝的基础；
2、只处理第 1 次遇到的那个数，举个具体的例子画个图。
重点理解：
1、 i > 0 ；
2、 nums[i] == nums[i - 1] ；
3、之前那个数还没有使用，即 marked[i-1] = false。
其实就是在 46 题的基础上做了重复检测。之前一个比较复杂的版本。下面是一个较简单的判断去重的版本，使用 Python 编写。
Python 代码：
# LeetCode 第 47 题：全排列问题 2
# 47. 全排列 II，要求：给定一个可包含重复数字的序列，返回所有不重复的全排列。
# 要去除重复，首先排序是肯定的
class Solution:
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) == 0:
return []
nums.sort()
used = [False] * len(nums)
res = []
self.__dfs(nums, 0, [], used, res)
return res
def __dfs(self, nums, index, pre, used, res):
if index == len(nums):
res.append(pre.copy())
return
for i in range(len(nums)):
if not used[i]:
# 如果没有用过
if i != 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True
pre.append(nums[i])
self.__dfs(nums, index + 1, pre, used, res)
used[i] = False
pre.pop()
if __name__ == '__main__':
s = Solution()
nums = [1, 1, 2]
result = s.permuteUnique(nums)
print(result)
Python 代码：
# LeetCode 第 47 题：全排列问题 2
# 47. 全排列 II，要求：给定一个可包含重复数字的序列，返回所有不重复的全排列。
# 要去除重复，首先排序是肯定的
class Solution:
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) == 0:
return []
nums.sort()
used = [False] * len(nums)
res = []
self.__dfs(nums, 0, [], used, res)
return res
def __dfs(self, nums, index, pre, used, res):
if index == len(nums):
res.append(pre.copy())
return
for i in range(len(nums)):
if not used[i]:
# 如果没有用过
if i != 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True
pre.append(nums[i])
self.__dfs(nums, index + 1, pre, used, res)
used[i] = False
pre.pop()
特别注意：1、排序；
2、if i != 0 and nums[i] == nums[i - 1] and not used[i - 1]: 这行代码中的 not used[i - 1] 这个条件很容易忘记；
3、continue 不是 break。
（本节完）
