题目难度：中等

题目描述：

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

数据范围： n<10 要求： 空间复杂度 O(n!)，时间复杂度 O(n!)

输入描述： 输入一个字符串,长度不超过10,字符只包括大小写字母。

示例1:

输入："ab" 返回值：["ab","ba"] 说明：返回["ba","ab"]也是正确的

思路：DFS

class Solution {
public:
  	// 标识是否已经访问
  	static const int N = 15;
  	bool st[N];
  	// 保存结果，和已经访问的排列
  	vector<string> res;
  	string path;
  
  	void dfs(const string& str, int index, int len) {
      	// base case
      	if (index == len) {
          	res.push_back(path);
          	return;
        }
      	for (int i = 0; i < len; ++i) {
          	// 判断重复的情况
          	// 1. 已经访问过；2.未访问，但是字符重复
          	// 这个限制条件保证了对于重复的字符，我们一定是从左往右依次填入的空位中的。
          	if (st[i] || i > 0 && !st[i-1] && str[i-1] == str[i]) continue;
          	st[i] = true;
          	path.push_back(str[i]);
          	dfs(str, index+1, len);
          	path.pop_back();
          	st[i] = false;
        }
    }
  
  	vector<string> Permutation(string str) {
      	if (str.length() == 0) return vector<string>({""});
      	// 初始化状态数组
      	memset(st, false, sizeof st);
      	// 排序，利于判断重复字符的情况
      	sort(str.begin(), str.end());
      	// 回溯 / 深度优先遍历
      	dfs(str, 0, str.length());
      	return res;
    }
}

😿😿😿😿