7.11全排列（LC46-M）

算法：

排列和组合很像，但是有顺序。

还是用回溯算法。

与组合不同之处（无startindex，有used数组）：

首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合。

可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。

但排列问题需要一个used数组，标记已经选择的元素

画树：

used在树中是一个int数组（Integer占4个字节），使用过的数字就标记为1.

但实际代码中可以用布尔数组（boolean占1个字节）表示。使用过的数字就标记：used[i] = true；这样下次循环中，若used[i] == true，就continue

回溯三部曲：

1.确定函数返回值和参数

返回值：void

参数：

int[] nums：题目给出

boolean[] used：标记是否用过该元素

2.确定终止条件

从树中可知，在叶子结点处收集结果

path.size() == nums.size()

3.单层递归逻辑（for循环）

若 used[i] == true, continue

used[i] = true

path.add(used[i]);

递归

回溯：

（1）path.removeLast()

（2）used[i] = false

调试过程：

原因：

``size()``方法用于获取列表中的元素数量，而``length``属性通常与数组一起使用，用于确定数组的长度。

在Java中，数组的长度是通过`length`属性来获取，而不是`size()`方法。这是因为数组是一个固定大小的数据结构，因此使用属性而不是方法来获取其长度更为合适。

因此，在这种情况下，`nums.length`是正确的，因为`nums`是一个数组，而不是一个列表。对于数组，使用`length`属性来获取其长度是标准的做法。

而对于`path`这样的列表，则需要使用`size()`方法来获取其长度。

正确代码：

class Solution {List<List<Integer>> result = new LinkedList<>();List<Integer> path = new LinkedList<>();public List<List<Integer>> permute(int[] nums) {boolean[] used2 = new boolean[nums.length]; backtracking (nums, used2);return result;}void backtracking (int[] nums, boolean[] used) {//确定终止条件if (path.size() == nums.length) {result.add (new LinkedList(path));return;}//单层递归逻辑，排序的i都从0开始了for(int i=0; i < nums.length; i++){if (used[i] == true) continue;//标记用过的数字used[i] = true;path.add(nums[i]);//递归backtracking (nums, used);//回溯，先入后出//先标记的used，那回溯时，used就后改path.removeLast();used[i] = false;}}
}