C++ dfs的状态表示（五十二）【第十二篇】

本文主要是介绍C++ dfs的状态表示（五十二）【第十二篇】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今天是对于之前的问题改进

1.k个数求和

对于前面 k 个数的和的求法，我们除了可以用上面的 DFS 方法以后，还有一种搜索策略。

之前的方法是每次去抉择是否选择第 
i 个数，现在我们的策略是从剩下的数中选择一个数。比如有 
5 个数 1,2,3,4,5，如果选择了 
1，那么剩下 2,3,4,5 四个数；如果选择了 2，那么剩下 1,3,4,5 四个数，还可以选择 3....；选择 
4....；选择 5.....。

代码实现起来很简单，我们标记每个数的是否被选择了。我们用 s 表示选出来的数的和，cnt 表示选出来的数的个数。

int n, k, sum, ans = 0, a[110];
bool xuan[110]; // 标记是否选择了
void dfs(int s, int cnt) {if (cnt == k) {if (s == sum) {ans++;}}for (int i = 0; i < n; i++) {if (!xuan[i]) {xuan[i] = true;dfs(s + a[i], cnt + 1);xuan[i] = false;}}
}

去除重复的方案

如果 int a[5] = {1, 2, 3, 4, 5}; 当 k&#

这篇关于C++ dfs的状态表示（五十二）【第十二篇】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---