一、题目
N
二、思路
【方法一】回溯+set
和全排列题目差不多的【回溯】套路，但是多了去重操作，比如aba的两个a视为相同的字符，即不能出现两个aab在结果vector中，最简单的方法就是在回溯模板上添个unordered_set去重后存入vector<string>中即可，但是这样木有剪枝，时间复杂度稍慢点。
【方法二】回溯+排序判断（剪枝法）
第二种去重方法是通过预处理实现去重：
（1）先对原字符串进行排序；
（2）然后确保相同字符传入同一目标位置的动作只发生一次。
【方法三】C++中next_permutation
但是一开始记得对字符串进行排序，因为next_permutation是以当前的字典序开始往下找下一个字典序的字符串，所以初始要是最小的字典序。如果木有排序则可能会漏解。
三、方法一：回溯+set
class Solution { private: unordered_set<string> s1; string temp; vector<string> ans; public: void generate(string s, vector<bool>& hashtable){ if(temp.size() == s.size()){ s1.insert(temp); return; } for(int i = 0; i < s.size(); i++){ if(hashtable[i] == false){ temp.push_back(s[i]); hashtable[i] = true; generate(s, hashtable); hashtable[i] = false; temp.pop_back(); } } } vector<string> permutation(string s) { vector<bool> hashtable(s.size(), false); generate(s, hashtable); for(auto& i: s1){ ans.push_back(i); } return ans; } };
四、方法二：回溯+剪枝
在树层上剪枝的效率更高，即用hashtable[i - 1] == false。
（1）hashtable[i - 1] == true，说明同一树枝s[i - 1]使用过，这里的树枝即一个节点；剪树枝只是剪了一个节点。
（2）hashtable[i - 1] == false，说明同一树层s[i - 1]使用过，则直接跳过，这里的树层即几个节点，这里为false则说明前一个树层递归完了撤销选择把hashtable[i-1]恢复为false，即表示前一个树层已经访问过了，和当前树层是重复的，需要剪枝。剪树层是剪了几个节点。
所以，如果要对树层中前一位去重，就用hashtable[i - 1] == false，如果要对树枝前一位去重用hashtable[i - 1] == true。
class Solution { private: //unordered_set<string> s1; string temp; vector<string> ans; public: void generate(string s, vector<bool>& hashtable){ if(temp.size() == s.size()){ ans.push_back(temp); return; } for(int i = 0; i < s.size(); i++){ if(i > 0 && s[i] == s[i - 1] && hashtable[i - 1] == false){ continue; } if(hashtable[i] == false){ temp.push_back(s[i]); hashtable[i] = true; generate(s, hashtable); hashtable[i] = false; temp.pop_back(); } } } vector<string> permutation(string s) { vector<bool> hashtable(s.size(), false); sort(s.begin(), s.end()); generate(s, hashtable); return ans; } };
五、方法三：next_permutation
偷鸡的方法，直接利用C++中next_permutation：
class Solution { public: vector<string> permutation(string s) { sort(s.begin(), s.end()); vector<string> ans; do{ ans.emplace_back(s); }while(next_permutation(s.begin(), s.end())); return ans; } };
