全排列问题是回溯的典型例题：
1.可行解的组成形式是给定数组中的所有数的组合，故而大小上可以作为可行解判定条件2.每次需要在剩下可被选中的集合中选择一个，创建mask数组class Solution {public: void dfs(vector > &vct, vector &cur, vector & nums,vector & used) { if (cur.size() == nums.size()) { vct.push_back(cur); return; } for (int i = 0; i < nums.size(); ++i) { if (used[i] == 0) { cur.push_back(nums[i]); used[i] = 1; dfs(vct, cur, nums, used); used[i] = 0; cur.pop_back(); } } } vector > permute(vector & nums) { vector > vct; int n = nums.size(); if (n <= 0) return vct; vector cur; vector used(n, 0); dfs(vct, cur, nums, used); return vct; }}; diff ： 需要考虑val1 = val2 的情况，需要sort将相同元素聚类，然后可以参考前文 去重的方法
class Solution {public: void dfs(vector > &vct, vector &cur, vector & nums, vector & used) { if (cur.size() == nums.size()) { vct.push_back(cur); return; } for (int i = 0; i < nums.size(); ++i) { if (used[i] == 0) { int pre_index = i - 1; bool repeated = false; while (pre_index >= 0 && nums[pre_index] == nums[i]) { if (used[pre_index] == 0) { repeated = true; break; } --pre_index; } if (repeated) continue; cur.push_back(nums[i]); used[i] = 1; dfs(vct, cur, nums, used); used[i] = 0; cur.pop_back(); } } } vector > permuteUnique(vector & nums) { vector > vct; vector cur; int n = nums.size(); if (n <= 0) return vct; vector used(n, 0); dfs(vct, cur, nums, used); return vct; }};