求解题思路和具体实现
今天老师布置了一道题，抽象出来就是这样的：
给你一个正整数T，n个正整数data[0]、data[1]、……data[n-1],要求在这n个数中选出几个数使得它们的和等于T.
输出所有的方案，如果没有的话，输出“NONE”.
我想用搜索的方法做，但思路比较混乱，没有写出代码来，请教各位前辈，给个思路以及实现代码。先谢谢了！
[解决办法]
1、对data进行排序，小的在后面，大的在前面。用一个数组记录排序后的位置对应于排序之前的位置。
2、从大到小依次尝试，用递归或者非递归的栈来做，比如排序后是{100，81，77,52,33,15}，T=200，则递归第一层从data[0]开始，一直到data[5]。第一层data[i1]确定后，第二层是从data[i1+1]开始到data[5]，依此类推。
3、如果递归过程中找到，则输出排序之前的位置即可。
[解决办法]
初始值为负无穷的01背包问题
[解决办法]
使用回溯法子集数搜索，能够列出所有的组合。这个问题也可以用背包问题去解决。这个版里面这个问题好多，你可以找找看看。
[解决办法]
直接深度搜索，具体见代码注释。
在解空间数中搜索
这是一个标准的子集和问题，没有多项式时间的解法，
只能搜，通过剪枝可以少搜一些路径。
// Subset.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;
vector<int> data; //存数组中数据
vector<int> solution; //存当前解
int T; //Target
int N; //总个数
int total; //当前解的总和
bool flag=0; //是否有满足条件的解
void dfs(int index)
{
if( index == N ) //递归到最后一层的下一层，结束了
{
if(total == T ) //如果解满足条件，输出
{
flag = 1;
for( int i=0; i<(int)solution.size();i++)
cout << solution[i] << " " ;
cout <<endl;
}
return;
}
if( total + data[index] <= T ) //将第index数加入解中，不会比目标大，则搜索加入第index数后的情况
{ //这里加入了目标约束来剪枝，删除一些不必要的搜索
total += data[index];
solution.push_back(data[index]);
dfs(index+1);
solution.pop_back(); //递归结束后还原状态
total -= data[index];
}
dfs(index+1); //搜索不加入第index数的情况
}
void input()
{
cout << "Please input N:" <<endl;
cin >> N;
cout << "Please input N integar number:" <<endl;
for( int i=0; i<N; i++)
{
int temp;
cin >> temp;
data.push_back(temp);
}
cout << "Please input T:" <<endl;
cin >> T;
}
int _tmain(int argc, _TCHAR* argv[])
{
input();
total =0;
dfs(0);
if( flag ==0 )
cout << "NONE" <<endl;
return 0;
}
