(step4.3.4)hdu 1258(Sum It Up——DFS)

题目大意:输入t，n，接下来有n个数组成的一个序列。输出总和为t的子序列

解题思路:DFS

代码如下(有详细的注释)：

#include <iostream>
#include <algorithm>
using namespace std;/**
 * t: 指定的和
 * n: 给出的数的个数
 * sign : 用来标记是否有解
 * index :结果序列中元素的个数
 * a[] :用来存储给出的数
 * save[] :用来保存结果序列
 *
 */
int t, n;
int a[20];
int save[20];
int index;
int sign;//降序排列
int cmp(const int &a, const int& b) {
return a > b;
}void dfs(int k, int sum) {
//如果当前搜索到的和>指定和
if (sum > t) {
return;
}
//如果当前搜索到的和 == 指定和
if (sum == t) {
sign = 1; //将sign标记为1,表示有解
for (int i = 0; i < index - 1; i++) {
cout << save[i] << "+";
}
cout << save[index - 1] << endl;
return;
}//遍历状态
int last = -1;
for (int i = k + 1; i <= n; i++) {
if (a[i] != last) { //当前的数不能跟上一次搜索的起点的数值一样，不然会造成重复
save[index++] = a[i];//将a[i]放进结果序列中
last = a[i];            //last保存当前搜索的起点
dfs(i, sum + a[i]);
index--;
}
}
}int main() {
int i;
while (cin >> t >> n, t + n) {
index = 0;
sign = 0;
for (i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1, cmp); //降序排序
printf("Sums of %d:\n", t);
dfs(0, 0);
if (!sign) {
cout << "NONE" << endl;
}
}
return 0;
}