使用递归的穷举搜索
Subsets 子集
https://cses.fi/problemset/task/1623
递归生成子集
编写一个递归函数，遍历所有可能的分组方式。
在某个索引处，我们要么将 $\texttt{apple}_i$ 添加到第一个集合，要么添加到第二个集合，存储两个总和 $\texttt{sum}_1$ 和 $\texttt{sum}_2$ ，分别表示每个集合中值的总和。
一旦到达数组的末尾，我们返回这两个总和的差值。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;int n;
vector<ll> apples;ll sol(int ind, ll sum1, ll sum2){if(ind == n){return abs(sum1 - sum2);}return min(sol(ind+1, sum1 + apples[ind], sum2),sol(ind+1, sum1, sum2 + apples[ind]));
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;apples.resize(n);for(int i = 0; i < n; i++){cin >> apples[i];}ll ans = sol(0, 0, 0);cout << ans;return 0;
}
Permutations 排列
- 排列是对一组元素的重新排序。
- Lexicographical Order 字典序
https://cses.fi/problemset/task/1622
Solution 1：递归生成排列
我们将使用递归函数 $\texttt{search}$ 来找出字符串 $s$ 的所有排列。首先，记录 $s$ 中每个字符的数量。对于每个函数调用，将一个可用字符添加到当前字符串中，并调用 $\texttt{search}$ 以该字符串作为参数。当当前字符串的长度与 $s$ 相同时，我们找到了一个排列，可以将其添加到 $\texttt{perms}$ 的列表中。
#include<bits/stdc++.h>
using namespace std;string str;
vector<string> ans;
int char_count[26];void search(string curr){if(curr.size() == str.size()){ans.push_back(curr);return;}for(int i = 0; i < 26; i++){if(char_count[i] > 0){char_count[i]--;search(curr + (char)('a' + i));char_count[i]++;}}
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin >> str;for(char c: str){char_count[c - 'a'] ++;}search("");cout << ans.size() << "\n";for(string str: ans){cout << str << "\n";}return 0;
}
Solution 2：使用 next_permutation 生成排列
或者，我们也可以直接使用 next_permutation() 函数。该函数接受一个范围，并将其修改为下一个更大的排列。如果没有更大的排列，它将返回 false。
每次调用 next_permutation 在遍历所有 $N!$ 大小的排列时，平均情况下会进行常数次交换。
#include<bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);string s;cin >> s;sort(s.begin(), s.end());vector<string> ans;do{ans.push_back(s);} while(next_permutation(s.begin(), s.end()));cout << ans.size() << "\n";for(string str: ans){cout << str << "\n";}return 0;
}
Backtracking 回溯法
https://cses.fi/problemset/task/1624
Solution 1：使用 next_permutation生成排列
一种检查所有 $\binom{64}{8}$ 种皇后组合的暴力解法将有超过 40 亿种情况需要检查，因此会太慢。
我们必须更聪明地进行暴力枚举：注意我们可以直接生成排列，使得任何两个皇后都不在同一行或同一列上互相攻击。
由于不能有两个皇后在同一列，因此只需要在每一行放置一个皇后。接下来需要确定的是如何变化每个皇后所在的行。这可以通过生成所有排列来实现，其中数字表示每个皇后所在的行。
#include<bits/stdc++.h>
using namespace std;int n = 8;
vector<vector<bool>>blocked(n, vector<bool>(n));
vector<int> queens(n);bool check(){for(int i = 0; i < n; i++){int j = queens[i];if(blocked[i][j]){return false;}}vector<bool> taken1(n * 2 - 1);for(int i = 0; i < n; i++){int sum = queens[i] + i;if(taken1[sum]){return false;}taken1[sum] = true;}vector<bool> taken2(n * 2 - 1);for(int i = 0; i < n; i++){int diff = queens[i] - i + n - 1;if(taken2[diff]){return false;}taken2[diff] = true;}return true;
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);for(int i = 0; i < n; i++){string s;cin >> s;for(int j = 0; j < n; j++){if(s[j] == '*'){blocked[i][j] = true;} else{blocked[i][j] = false;}}}iota(queens.begin(), queens.end(), 0);int ans = 0;do{if(check()){ans++;}} while(next_permutation(queens.begin(), queens.end()));cout << ans;return 0;
}
Solution 2：使用回溯法
回溯算法从一个空解开始，逐步扩展解。搜索递归地遍历所有可能的解的构造方式。
由于边界条件较小，我们可以递归地回溯所有放置皇后的方式，并存储棋盘的当前状态。
在每一层，我们尝试在所有未被阻挡或未被其他皇后攻击的格子上放置皇后。完成这一步后，我们递归调用，然后移除该皇后并回溯。
最后，当我们将八个皇后全部放置完毕时，我们增加答案计数。
#include<bits/stdc++.h>
using namespace std;int n = 8;
vector<vector<int>> blocked(n, vector<int>(n));
int ans = 0;
vector<bool> row_taken(n);
vector<bool> diag1(2 * n - 1);
vector<bool> diag2(2 * n - 1);void search_queens(int j){if(j == n){ans++;return;}for(int i = 0; i < n; i++){if(!blocked[i][j] && !row_taken[i] && !diag1[i+j] && ! diag2[i-j+n-1]){row_taken[i] = diag1[i+j] = diag2[i-j+n-1] = true;search_queens(j+1);row_taken[i] = diag1[i+j] = diag2[i-j+n-1] = false;}}
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);for(int i = 0; i < n; i++){string s;cin >> s;for(int j = 0; j < n; j++){blocked[i][j] = s[j] == '*';}}search_queens(0);cout << ans;return 0;
}