（递归+回溯+剪枝）面试题 08.08. 有重复字符串的排列组合

难度：中等

思考：

这道题主要用到位置交换的的思想，重点是对于同一个位置，如果两个元素相同，那么只能把这个元素放在这个位置一次，否则会造成重复，所以在剪枝操作的时候需要特别注意。

 1 //通过字符串之间的顺序置换，来得到不同的字符串
 2 class Solution {
 3     vector<string> res;
 4     int n = 0;
 5 public:
 6     vector<string> permutation(string S) {
 7         sort(S.begin(), S.end());
 8         n = S.size();
 9         dfs(S, 0);
10         return res;
11     }
12     void dfs(string S, int start){
13         if(start == n - 1){
14             res.push_back(S);
15             return;
16         }
17         for(int i = start; i < n; i ++){
18             //剪枝操作，如果i>start的时候，存在两种情况
19             //第一种：要交换的两个元素是重复的，那么就不需要交换，即：i > start && S[start] == S[i]
20             //第二种：两次交换的元素是重复的，那么也不需要交换：即：i > start && S[i] == S[i-1]
21             if(i > start && (S[start] == S[i] || S[i] == S[i-1]))
22                 continue;
23             swap(S[i], S[start]);
24             dfs(S, start+1);
25             swap(S[i], S[start]);
26         }
27     }
28 };