基本思想：
崩溃了，主要还是有两个问题：
1.存在剪枝问题，不剪枝会超时；
2.DFS写法的问题，感觉OJ里特别喜欢通过返回true false，来进行多循环的一次递归解决所有问题；
bool dfs(int n,int index,int value,int num) {
if (num == 3)
return true;
for (int i = index; i < n; i++) {
if (!vis[i]) {
vis[i] = true;
if (vec[i] + value == cnt) {
if (dfs(n, 0, 0, num+1))
return true;
}
else if (vec[i] + value < cnt) {
if (dfs(n, i+1, vec[i] + value, num))
return true;
}
vis[i] = false;
}
}
return false;
}
以上述代码为例，通过一次递归进入来获得所有的结果；
首先进行排序，保证从大的选起，从而不会发生小的选完大的无法适配的情况，这个自己当时也看出来了；
总的来说，是通过三次迭代进行计算，每次迭代通过递归遍历来找到满足条件的情况；
当时卡在了如何把这三次迭代连起来，自己采用for循环循环三次，还是超时了；
大佬的代码是通过当第一次情况满足的时候，直接递归套入新的一层迭代，并且由于vis数组不改变，所以可以看作再前一次的基础上进行继续寻找；
其次，利用num来进行迭代次数监控，当num=3的时候，直接开头就return true；
整体后续的判断是否正确都可以通过return来反应到第一层，所以就会得知是否能够找到成功的情况。可以看作是前一道DFS的升级版，需要分层；
关键点：
剪枝问题；
#include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; const int maxn = 22; bool vis[maxn]; vector<int>vec; int cnt;//边长 void init(int n) { fill(vis, vis + n, false); vec.resize(n); //correct = 0; cnt = 0; } bool cmp(int a, int b) { return a > b; } bool dfs(int n,int index,int value,int num) { if (num == 3) return true; for (int i = index; i < n; i++) { if (!vis[i]) { vis[i] = true; if (vec[i] + value == cnt) { if (dfs(n, 0, 0, num+1)) return true; } else if (vec[i] + value < cnt) { if (dfs(n, i+1, vec[i] + value, num)) return true; } vis[i] = false; } } return false; } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { int m; cin >> m; init(m); for (int i = 0; i < m; i++) { cin >> vec[i]; cnt += vec[i]; } if (cnt % 4 != 0) { cout << "no" << endl; continue; } cnt /= 4; sort(vec.begin(), vec.end(), cmp); if (vec[0] > cnt) { cout << "no" << endl; continue; } //dfs(n, 0, vec[0]); if (dfs(m,0,0,0)) cout << "yes" << endl; else cout << "no" << endl; } return 0; }
原文：https://www.cnblogs.com/songlinxuan/p/12446189.html