Subset sum Problem

给出一个集合和一个数值total，输出用哪几个数可以组出total。

参考链接：http://algorithms.tutorialhorizon.com/dynamic-programming-subset-sum-problem/

DP方程为 dp[i][j]=

dp[i-1][j] if a[j]>jdp[i-1][j-a[j]] if a[j]<=j

方程的形式同背包问题如出一辙，只不过这个不涉及到重量、价值问题，而只涉及能不能放下【确切的说应该是放满】

本来是想拿这个去做Combination Sum的，发现那个是回溯而并不是DP。

至于取出所有可能的集合，我写了一个DFS去递归寻找可能的解。 不过可能不是很严谨

正确求法：

Start from the bottom-right cor­ner and back­track and check from the True is coming.If value in the cell above if false that means cur­rent cell has become true after includ­ing the cur­rent ele­ment. So include the cur­rent ele­ment and check for the sum = sum — cur­rent element.

class Solution { public: // bool dp[n][target+1];//dp[i][j]表示放入前i个物品,容量为j的时候最大价值 bool dp[1010][1010]; vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { //01背包 int n=candidates.size(); //使之有序 sort(candidates.begin(),candidates.end()); memset(dp,0,sizeof(dp)); //初始化第一行数据 for(int i=0;i<n;i++) dp[i][0]=true; for(int i=0;i<n;i++){ //背包容量遍历 for(int j=1;j<=target;j++){ if(candidates[i]==j) dp[i][j]=true; else if(candidates[i]>j) dp[i][j]=dp[i-1][j]; else{ if(i>0) dp[i][j]=dp[i-1][j-candidates[i]]; else dp[i][j]=false; } } } for(int i=0;i<n;i++){ //背包容量遍历 for(int j=1;j<=target;j++){ printf("%d ",dp[i][j]); } printf("\n"); } printf("\n"); vector<vector<int> > result; vector<int> temp; dfs(temp,candidates,n-1,target,result); return result; // //得到dp数组之后，需要遍历一下dp[i][target]==true的地方开始，向后回溯找所有的数值 } void dfs(vector<int> &temp,vector<int>& candidates,int start,int capacity,vector<vector<int> >& result){ //已经装满了 if(capacity==0){ result.push_back(temp); return; } //从后往前找 for(int i=start;i>=0;i--){ //说明这一栏是true if(dp[i][capacity]){ //防止从后往前 // if(capacity-candidates[i] <= candidates[i]){ temp.push_back(candidates[i]); dfs(temp,candidates,start-1,capacity-candidates[i],result); temp.pop_back(); // } } } } };