【全排列】回溯算法入门

• 案例一：无重数组全排列：
• 算法介绍：
• 
• 利用树形图判断递归结构与如何剪枝：
• 分支如何产生
• 题目需要的解在叶子节点还是非叶子节点，还是路径？
• 哪些情况下会产生不必要的解：
• 为什么产生
• 如何剪枝
• 代码：
• 
  class Solution { vector> res;private: void perm(vector& nums, int low, int high) { if (low == high) { res.emplace_back(nums); return; } for (int i = low; i <= high; ++i) { swap(nums[i], nums[low]); perm(nums, low + 1, high); swap(nums[i], nums[low]); } }public: vector> permute(vector& nums) { res.clear(); perm(nums, 0, nums.size() - 1); return res; }};
• 案例二：带有重复数的全排列（剪枝）：
• 算法介绍：
• 本题为上述题目的plus版，序列中包含重复的数字，要求返回不带重复数字的全排列，我们依然采用回溯方法
• 首先要对元素进行排序，以便我们通过相邻的节点判断是否重复使用
• 对于搜索树的同一层进行去重：
• 
• 回溯算法是先按照dfs的搜索顺序搜索出一个有效解，再不断回溯到可以探索的搜索空间，因此对于搜索树的同一层来说，如果used[i - 1] == false，那么该位置放置nums[i]的解已经搜索完毕，因此可以跳过
• 使用used[i - 1] == true也可以，对于同一路径去重，但搜索效率不如以上方法高
• 
• 代码： class Solution {private: vector> res; vector path; void backtracking(vector& nums, vector& used) { if (path.size() == nums.size()) { res.emplace_back(path); return; } for (int i = 0; i < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue; if (used[i] == false) { used[i] = true; path.emplace_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] = false; } } }public: vector> permuteUnique(vector& nums) { res.clear(); path.clear(); vector used(nums.size(), false); sort(nums.begin(), nums.end()); backtracking(nums, used); return res; }};