常见经典递归总结
子集枚举
题目 1 返回字符串的全部字序列
时间复杂度：$O(n*2^n)$(子集枚举+遍历)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool st[20];
set<string> set_str;
void dfs(int x, string& str){
if (x >= str.size()){
string temp;
for(int i = 0; i < str.size(); i++){ // 遍历子集
if (st[i]){
temp.push_back(str[i]);
}
}
set_str.insert(temp);
return;
}
st[x] = true;
dfs(x + 1, str); // 选
st[x] = false;
dfs(x + 1, str); // 不选
}
vector<string> generatePermutation(string s) {
dfs(0, s);
vector<string> ans;
for(auto it : set_str){
ans.push_back(it);
}
return ans;
}
题目 2 子集 II
时间复杂度：$O(n*2^n)$(子集枚举+遍历)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool stat[100]; // 存储状态
set<vector<int>> st;
void dfs(int x, vector<int> &nums) {
if (x >= nums.size()) {
vector<int> temp;
for (int i = 0; i < nums.size(); i++) { // 遍历子集
if (stat[i]) {
temp.push_back(nums[i]);
}
}
st.insert(temp);
return;
}
stat[x] = true;
dfs(x + 1, nums); // 选
stat[x] = false;
dfs(x + 1, nums); // 不选
}
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
dfs(0, nums);
for (auto it : st) {
ans.push_back(it);
}
return ans;
}
排列
题目 1 全排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
vector<vector<int>> ans;
int arr[100];
int st[100];
void dfs(int x, vector<int> &nums) {
int n = nums.size();
if (x >= n) {
vector<int> temp;
for (int i = 0; i < n; i++) {
int idx = arr[i];
temp.push_back(nums[idx]);
}
ans.push_back(temp);
return;
}
for (int i = 0; i < n; i++) {
if (st[i]) {
continue;
}
st[i] = 1;
arr[x] = i;
dfs(x + 1, nums);
st[i] = 0;
arr[x] = 0;
}
}
vector<vector<int>> permute(vector<int> &nums) {
dfs(0, nums);
return ans;
}
题目 2 全排列 II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
set<vector<int>> set_vec;
vector<vector<int>> ans;
int arr[100];
bool st[100];
void dfs(int x, vector<int> &nums) {
int n = nums.size();
if (x >= n) {
vector<int> temp;
for (int i = 0; i < n; i++) {
int idx = arr[i];
temp.push_back(nums[idx]);
}
set_vec.insert(temp);
return;
}
for (int i = 0; i < n; i++) {
if (st[i]) {
continue;
}
st[i] = true;
arr[x] = i;
dfs(x + 1, nums);
st[i] = false;
arr[x] = 0;
}
}
vector<vector<int>> permuteUnique(vector<int> &nums) {
dfs(0, nums);
for (auto it : set_vec) {
ans.push_back(it);
}
return ans;
}
只用递归函数逆序栈
时间复杂度：$O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int bottomOut(stack<int> &stk) { // 操作：将栈底元素返回，并保持其它元素顺序不变
int ans = stk.top();
stk.pop();
if (stk.empty()) {
return ans;
}
int last = bottomOut(stk);
stk.push(ans);
return last;
}
void reverse(stack<int> &stk) { // 利用操作逆序栈
if (stk.empty()) {
return;
}
int num = bottomOut(stk);
reverse(stk);
stk.push(num);
}
只用递归函数排序栈
时间复杂度：$O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int deep(stack<int> &stk) { // 操作：返回栈深度不改变栈状态
if (stk.empty()) {
return 0;
}
int num = stk.top();
stk.pop();
int deep = deep(stk) + 1;
stk.push(num);
return deep;
}
int max(stack<int> &stk, int deep){
if(deep == 0){
return INT_MIN;
}
int num = stk.top();
int resMax = max(stk, deep - 1);
stk.pop();
int max = max(num, resMax);
stk.push(num);
return max;
}
int times(stack<int> &stk, int deep, int max){
if(deep == 0){
return 0;
}
int num = stk.top();
stk.pop();
int restTimes = times(stk, deep - 1, max);
int times = resetTimes + (num == max ? 1 : 0);
stk.push(num);
return times;
}
void down(stack &stk, int deep, int max, int k){
if(deep == 0){
for(int i = 0; i < k; i++){
stk.push(max);
}
}else{
int num = stk.top();
stk.pop();
down(stk, deep - 1, max, k);
if(num != max){
stk.push(num);
}
}
}
void sortStack(stack<int> &stk) {
int deep = deep(stk);
int max = max(stk, deep);
int times = times(stk, deep, max);
down(stk, deep, max, times);
reverse(stk);
}
汉诺塔问题
时间复杂度：$O(2^n)$
1
2
3
4
5
6
7
8
9
void f(int i, int from, int to, int other){
if(i == 1){
cout << "移动原盘 1 从" << from << "到" << to << endl;
}else{
f(i - 1, from, other, to);
cout << "移动圆盘" << i << "从" << from << "到" << to << endl;
f(i - 1, other, to, from);
}
}
