一、全排列
遞歸暴力DFS：
面試中，排列組合的實作是需要掌握的。一般最先想到的方法是暴力循環法，即對于每一位，周遊集合中可能的元素，如果在這一位之前出現過了該元素，跳過該元素。例如對于
abc
，第一位可以是 a 或 b 或 c 。當第一位為 a 時，第二位再周遊集合，發現 a 不行，因為前面已經出現 a 了，而 b 和 c 可以。當第二位為 b 時 ， 再周遊集合，發現 a 和 b 都不行，c 可以。可以用遞歸或循環來實作，但是複雜度為 O(nn) 。
1 void permutation1(string src, string path, vector<string>& res) {
2 if (path.size() == src.size()) {
3 res.push_back(path);
4 return;
5 }
6 int len = src.length();
7 for (int i = 0; i < len; i++) {
8 if (path.find(src[i]) == string::npos) {
9 path.push_back(src[i]);
10 permutation1(src, path, res);
11 path.pop_back();
12 }
13 }
14 }
15
16 vector<string> permutation(string src) {
17 vector<string> res;
18 permutation1(src, "", res);
19 return res;
20 } 交換：
首先考慮
bac
和
cba
這二個字元串是如何得出的。顯然這二個都是
abc
中的 a 與後面兩字元交換得到的。然後可以将
abc
的第二個字元和第三個字元交換得到
acb
。同理可以根據
bac
cba
來得
bca
cab
。是以可以知道 全排列就是從第一個數字起每個數分别與它後面的數字交換，也可以得出這種解法每次得到的結果都是正确結果，是以複雜度為 O(n!)。
1 void permutation2(string src, int start, vector<string>& res) {
2 int n = src.size();
3 if (start == n - 1) {
4 res.push_back(src);
5 return;
6 }
7
8 for (int i = start; i < n; i++) {
9 std::swap(src[start], src[i]);
10 permutation2(src, start + 1, res);
11 std::swap(src[start], src[i]);
12 }
13 } 去重的全排列
有時候給出的src中出現重複的字元，類如abb。按照上面的排列方法得出的結果裡面會有重複的字元串。為了得到不一樣的排列，去重的全排列要從第一個數字起每個數分别與它後面非重複出現的數字交換。用程式設計的話描述就是第i個數與第j個數交換時，要求[i,j)中沒有與第j個數相等的數
1 void permutation3(string src, int start, vector<string>& res) {
2 int n = src.size();
3 if (start == n - 1) {
4 res.push_back(src);
5 return;
6 }
7
8 for (int i = start; i < n; i++) {
9 bool isRepeated = false;
10 for (int j = start; j < i; j++) {
11 if (src[j] == src[i]) {
12 isRepeated = true;
13 break;
14 }
15 }
16 if (!isRepeated) {
17 std::swap(src[start], src[i]);
18 permutation2(src, start + 1, res);
19 std::swap(src[start], src[i]);
20 }
21 }
22 } 二、組合
DFS暴力枚舉：
1 void combination2(string src, int start, string path, vector<string>& res) {
2 int len = src.length();
3 if (start == len) {
4 if (!path.empty()) {
5 res.push_back(path);
6 }
7 return;
8 }
9 combination2(src, start + 1, path, res);
10 path.push_back(src[start]);
11 combination2(src, start + 1, path, res);
12 }
13
14 vector<string> combination2(string src) {
15 if (src.empty())
16 return {};
17 vector<string> res;
18 combination2(src, 0, "", res);
19 return res;
20 } 二進制法：
1 //二進制法
2 vector<string> combination(string src) {
3 if (src.empty())
4 return {};
5 int len = src.length();
6 int n = 1 << len;
7 vector<string> res;
8 for (int i = 0; i < n; i++) {
9 string tmp;
10 for (int j = 0; j < len; j++) {
11 if (i & (1 << j)) {
12 tmp.push_back(src[j]);
13 }
14 }
15 if (!tmp.empty()) {
16 res.push_back(tmp);
17 }
18 }
19 return res;
20 }