求和替定值的数组的子集

求和为定值的数组的子集
一个数组 {2,3,7,4,8}
求和为7的子集，一共两个{3,4},{7}
这个怎么弄？

[解决办法]
子集和问题。
[解决办法]
用回溯法做。
[解决办法]
我给写了个。

C/C++ code

#include <iostream>#include <string>#include <stack>#include <vector>using namespace std;/*使用回溯法解子集和问题*/const int N=5;int arr[]={2,3,4,7,8};int sum=7;int total=0;vector<int> solution;bool hasResult = false;void dfs( int index ){    if( index==N ){                        //递归到最后一层的下一层，结束        if( total==sum ){                  //判断是否满足条件，满足则输出结果            hasResult = true;            for(int i=0; i<(int)solution.size();i++)                cout<<solution[i]<<" ";            cout <<endl;        }        return;    }    if( total + arr[index] <= sum ){          //加入第index个数是否小于总和，是则加入        total += arr[index];        solution.push_back(arr[index]);        dfs(index+1);        solution.pop_back();                 //回溯，还原状态        total -= arr[index];    }    dfs(index+1);                       //递归搜索未加入第index个数字的情况}int main(){    dfs(0);    if( !hasResult )        cout << "NO SOLUTION!" <<endl;    return 0;}
[解决办法]
void dfs( int index )
{
   if( index==N ){                        //递归到最后一层的下一层，结束
       if( total==sum ){                  //判断是否满足条件，满足则输出结果
           hasResult = true;
           for(int i=0; i<(int)solution.size();i++)
               cout<<solution[i]<<" ";
           cout <<endl;
       }
       return;
   }

   if( total + arr[index] <= sum ){          //加入第index个数是否小于总和，是则加入
       total += arr[index];
       solution.push_back(arr[index]);
       dfs(index+1);
       solution.pop_back();                 //回溯，还原状态
       total -= arr[index];
   }

   dfs(index+1);                       //递归搜索未加入第index个数字的情况
}