#include <cstdio>
/** 假设我们有8种不同面值的硬币{1,2,5,10,20,50,100,200},用这些硬币组合构成一个给定的数值n。* 例如n=200,那么一种可能的组合方式为：200 = 3*1 + 1*2 + 1*5 + 2*20 + 1*50 + 1*100.* 问总共有多少种可能的组合方式？*/int coins[4] = {1,5,10,15};// n是当前剩余金币数,cur是能取的最大额度的index
int fn(int n,int cur){if(cur==0)return 1;int res = 0;for (int i = 0; i * coins[cur] <= n; ++i) {int rm = n - i * coins[cur];  // 剩余res += fn(rm, cur-1);}return res;
}int main(){printf("%d", fn(15, 3));return 0;
}

括号问题

#include <cstdio>
#include <set>
#include <string>using namespace std;// 实现一种算法，打印n对括号的全部有效组合（即左右括号正确配对）
// 如 3 : ((())),(()()),(())(),()(()),()()()set<string> fn(int n){set<string> s_n;if(n==1){s_n.insert("()");return s_n;}set<string> s = fn(n-1);for (string str : s){s_n.insert("()" + str);s_n.insert(str + "()");s_n.insert("(" + str + ")");}return s_n;
}int main(){set<string> res = fn(4);for (set<string>::iterator it = res.begin(); it != res.end(); it++) {printf("%s,", (*it).c_str());}return 0;
}

集合问题

#include <cstdio>
#include <set>using namespace std;int a[3] = {1, 2, 3};set<set<int>> getSubsets(int cur){set<set<int>> newset;if(cur == 0){set<int> nil;set<int> first;first.insert(a[0]);newset.insert(nil);newset.insert(first);return newset;}set<set<int>> oldset = getSubsets(cur-1);for(set<int> ss: oldset){newset.insert(ss);set<int> cset = ss;cset.insert(a[cur]);newset.insert(cset);}return newset;
}int main(){set<set<int>> res = getSubsets(2);for (set<int> ss: res){printf("{");for (int num : ss){printf("{%d}",num);}printf("},");}return 0;
}

二进制法

#include <cstdio>
#include <cmath>
#include <vector>using namespace std;int a[3] = {1, 2, 3};// 111 => 3,2,1
// 101 => 3,1
vector<vector<int>> getSub(int n){vector<vector<int>> res;int ex = pow(2, n) - 1;for (int i = ex; i > 0; i--) {vector<int> v;for (int j = n - 1; j >= 0; j--) {if(((i >> j) & 1)==1){v.push_back(a[j]);}}res.push_back(v);}return res;
}int main(){vector<vector<int>> res = getSub(3);for(vector<int> v : res){printf("{ ");for (int num: v){printf("%d ", num);}printf("},");}return 0;
}

全排列

// 注意：C++中有专门的函数

#include <cstdio>
#include <vector>
#include <string>using namespace std;char arr[3] = {'A', 'B', 'C'};
int length = 3;
vector<string> v;// 第一种全排列的方法
void getPermutaion(int k){if(k == length){v.push_back(arr);}for (int i = k; i < length; ++i) {swap(arr[k], arr[i]);getPermutaion(k+1);swap(arr[k], arr[i]);}
}
// -------------------int getCount(string s, char c){int count = 0;for (int i = 0; i < s.length(); ++i) {if(s[i]==c){count++;}}return count;
}int getCount(char s[], char c){int count = 0;for (int i = 0; i < length; ++i) {if(s[i]==c){count++;}}return count;
}int k = 3;
int count = 0;// 第二种(求第k个全排列),也可求全部的(按字典序排列)
void getPermutaion(string prefix){if(prefix.length()==length){count++;printf("%s\t", prefix.c_str());
//        if(count==k){
//          printf("%s", prefix.c_str());
//            return;
//        }}for (int i = 0; i < length; ++i) {char ch = arr[i];if(getCount(prefix, ch) < getCount(arr, ch)){getPermutaion(prefix + ch);}}
}int main(){getPermutaion(0);for (int i = 0; i < v.size(); ++i) {printf("%s\t", v[i].c_str());}printf("\n");getPermutaion("");return 0;
}

dfs

二进制的方法做

#include <cstdio>
#include <iostream>
/** 给定整数序列a1,a2,...,an,判断是否可以从中选出若干数，使它们的和恰好为k.* 1<=n<=20* -10^8<=ai<=10^8* -10^8<=k<=10^8**/
int n;
int k;void fn(int a[]){int mm = (1 << n) - 1;for (int i = mm; i > 0; i--) {int sum = 0;int count = 0;for (int j = 0; j < n; ++j) {if(((i>>(n-j-1))&1)==1){  // i的第(n-j-1)位为1sum+=a[j];count++;}if(sum>k){break;}}if(sum==k){for (int j = 0; j < n; ++j) {if(((i>>(n-j-1))&1)==1){count--;if(count){printf("%d+", a[j]);}else{printf("%d", a[j]);}}}exit(0);}}
}int main(){// n = 4// a = {1, 2, 4, 7}// k = 13scanf("%d", &n);int a[n];for (int i = 0; i < n; ++i) {scanf("%d", &a[i]);}scanf("%d", &k);fn(a);return 0;
}

dfs

#include <cstdio>
#include <iostream>
/** 给定整数序列a1,a2,...,an,判断是否可以从中选出若干数，使它们的和恰好为k.* 1<=n<=20* -10^8<=ai<=10^8* -10^8<=k<=10^8**/
int n;
int k;void dfs(int a[], int k, int cur){if(k == 0){printf("Yes");exit(0);}if(k < 0 || cur == n){return;}dfs(a, k, cur + 1);  // 不选当前元素dfs(a, k - a[cur], cur + 1);  // 选当前元素
}int main(){scanf("%d", &n);int a[n];for (int i = 0; i < n; ++i) {scanf("%d", &a[i]);}scanf("%d", &k);dfs(a, k, 0);return 0;
}

#include <cstdio>int n, m;char a[100][100];void dfs(int i, int j){a[i][j] = '.';for (int k = -1; k <= 1; ++k) {for (int l = -1; l <= 1; ++l) {if(k==0&&l==0){continue;}if(i+k>=0&&i+k<=n-1&&j+l>=0&&j+l<=m-1){if(a[i+k][j+l]=='W'){dfs(i+k,j+l);}}}}
}int main(){scanf("%d%d", &n,&m);// 读字符串for (int i = 0; i < n; ++i) {scanf("%s",a[i]);}int cnt = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if(a[i][j]=='W'){dfs(i, j);cnt++;}}}printf("%d", cnt);return 0;
}

困难的串

#include <cstdio>
#include <string>using namespace std;/** 问题描述：如果一个字符串包含两个相邻的重复子串，则称它为容易的串，其他串称为困难的串，* 如：BB, ABCDACAABCAB,ABCDABCD都是容易的，A, AB, ABA, D, DC, ABDAB, CBABCBA都是困难的。* 输入正整数n,L, 输出由前L个字符（大写英文字母）组成的，字典序第n小的困难的串。* 例如，当L=3，前7个困难的串分别为：* A,AB,ABA,ABAC,ABACA,ABACAB,ABACABA*/int l = 3, n = 7, count = 0;// substr()的第二个参数为长度,如果不写,则直接截取到末尾。
bool isHard(string s){int len = s.length();string s1, s2;for (int i = 1; i <= len/2; ++i) {int start = len - i;s1 = s.substr(start);s2 = s.substr(start - i, i);if(s1==s2) return false;}return true;
}void dfs(string prefix){for (char i = 'A'; i < 'A' + l; i++) {if(isHard(prefix+i)){string x = prefix + i;printf("%s\n", x.c_str());count++;if(count == n){exit(0);}dfs(x);}}
}int main(){dfs("");return 0;
}