全排列有两种枚举程序：
（1）按程序枚举每个地位填哪个数
（2）按程序枚举每个数填哪个地位

两种程序都能解，但如果要保障字典序，则须要应用（1）按程序枚举每个地位填哪个数。因为优先思考将小的数放到后面地位。

leetcode 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]]

提醒：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不雷同

计划：采纳（1）按程序枚举每个地位填哪个数

class Solution {    List<Integer> path = new ArrayList<>();    List<List<Integer>> ans = new ArrayList<>();;    public List<List<Integer>> permute(int[] nums) {        dfs(nums, 0, 0);        return ans;    }    // u:坑位，按程序枚举每个坑位填哪个数    public void dfs(int[] nums, int u, int state) {        if (u == nums.length) {            ans.add(new ArrayList<>(path));            return;        }        for (int i = 0; i < nums.length; i++) { //枚举每个数            if ((state >> i & 1) == 0) {                 path.add(nums[i]);                dfs(nums, u + 1, state + (1 << i));                path.remove(path.size() - 1);            }        }    }}

leetcode 47. 全排列 II

给定一个可蕴含反复数字的序列 nums ，按任意程序 返回所有不反复的全排列。

示例 1：
输出：nums = [1,1,2]
输入：
[[1,1,2],
[1,2,1],
[2,1,1]]

提醒：
1 <= nums.length <= 8
-10 <= nums[i] <= 10

办法1：[顺次枚举每个数，看能填到哪些坑位上]

class Solution {public:    vector<vector<int>> ans;    vector<int> path;    vector<vector<int>> permutation(vector<int>& nums) {        sort(nums.begin(), nums.end());        path.resize(nums.size());        dfs(nums, 0, 0, 0);        return ans;    } // u:枚举到第几个数 start:上一个数的坑位在哪 state: 标记坑位是否被占    void dfs(vector<int> &nums, int u, int start, int state) {        if (u == nums.size()) {            ans.push_back(path);            return;        }        if (!u || nums[u] != nums[u - 1]) start = 0; //下一个反复元素只能放在前面，有序性。其余都从第0个坑位开始看是否填        for (int i = start; i < nums.size(); i ++) //枚举坑位，看是否填上nums[u]            if (!(state >> i & 1)) {                path[i] = nums[u];                dfs(nums, u + 1, i + 1, state + (1 << i));            }    }};

此处i:坑位，u:第几个数。此处和上一题不一样！上一题是顺次枚举每个坑位看能填哪些数，而此题是顺次枚举每个数，看能填到哪些坑位上。（因为此题顺次枚举每个数能够判断反复数字，反复的只能放到上一个反复填的坑位之后）
链接：https://www.acwing.com/activi...

解法2：【第u坑位枚举每个数是否填，即按程序枚举每个地位填哪个数】

vector<vector<int>> ans;vector<int> path;vector<bool> st;void dfs(vector<int>& nums, int u) {    if (u == nums.size()) {        ans.push_back(path);        return;    }    for (int i = 0; i < nums.size(); i++) // 顺次枚举每个数，所以能够规定雷同数的程序        if (!st[i]) {            if (i && (nums[i] == nums[i - 1]) && !st[i - 1]) // 用第一次没有用过的雷同数，不能跳。则程序就定下来了                continue;            st[i] = true;            path[u] = nums[i]; // 因为顺次枚举每个地位填哪个数，故u递增也能够应用path.push_back(nums[i]);            dfs(nums, u + 1);            st[i] = false;     // 此时就须要path.pop_back();        }}vector<vector<int>> permuteUnique(vector<int>& nums) {    sort(nums.begin(), nums.end());    st = vector<bool>(nums.size(), false);    path = vector<int>(nums.size());    dfs(nums, 0);    return ans;}

又回来看一遍视频，讲的切实太好了，有两句最外围的内容，我加上本人的了解整顿写了一下。
A 1分24秒到2分00秒：讲了为什么要先排序 因为后果是要去重的，而后果都是列表模式的，那列表怎么判重呢？就是排序之后一个一个的比拟，所以那还不如先排序之后再计算，再计算的过程中判断是否有反复，省得对每个后果再做一次排序去重操作。
B 2分25秒到4分10秒：讲了怎么判断以后分支是否是反复的分支。 因为之前曾经排好序了，所以以后元素nums[i] 如果和前一个元素雷同，即nums[i] == nums[i-1]就阐明该分支有可能是反复的。然而这个相等条件有两种可能一种是，1 1‘ 2，也就是抉择完1之后再抉择第二个1，两个元素尽管反复，然而第二个元素是前一个元素的下一层，这时是没有问题的。另一种是之前的同层分支曾经有 1 1‘ 2了，这次的抉择是 1‘ 1 2 。两个元素反复，且重的是同层门路。那就阐明是反复分支。
具体辨别的方法是 nums[i-1] 的used状态是被抉择的，那么阐明以后的nums[i] 是 nums[i-1]的下一层门路。否则如果 nums[i-1] 的状态是没被抉择的，那么阐明以后的nums[i] 是nums[i-1] 同层门路。

有内鬼终止AC
2021-10-01
@GB2312 说的太好了，补充一下
为什么" nums[i-1] 的used状态是被抉择的，那么阐明以后的nums[i] 是 nums[i-1]的下一层门路。"
起因：因为往上层递归的话，始终再往上层走，dfs还未return，也就是说used还没有被回溯为未抉择状态，所以同一条分支上，nums[i-1] 的used状态肯定是被抉择的。
为什么" 如果 nums[i-1] 的状态是没被抉择的，那么阐明以后的nums[i] 是nums[i-1] 同层门路。"
起因：递归到叶节点，开始往上回溯了，回溯到某一层时把used[i-1]回溯为未抉择状态，而后for循环i++横向挪动，天然这时再判断used[i-1]就肯定是未抉择状态。

因为咱们是枚举每个坑位填哪个数，所以雷同数的枚举到的程序必定是顺次的，不能也不会跳过！

PS:两种解法中排序的目标不是让数组有序，而只是让雷同的数放在一起。