无穷背包?
输入2 3 6 7
输出2 3 6 7所有能构成7的情况。
int cmp(int a,int b) { return a < b; } struct ValNode { ValNode():IsExist(false){set_v.clear();} vector<vector<int>>set_v; bool IsExist; }; class Solution { public: bool CheckIsExist(vector<int>&item_tmp,vector<vector<int>>&set_v) { sort(item_tmp.begin(),item_tmp.end(),cmp); for(int i = 0;i < set_v.size();i++) { if(item_tmp == set_v[i])return true; } return false; } vector<vector<int> > combinationSum(vector<int> &candidates, int target) { int max = target; ValNode *valnodes = new ValNode[max+1]; valnodes[0].IsExist = true; vector<int>item; item.clear(); valnodes[0].set_v.push_back(item); for(int i = 0;i <= target;i++) { if(valnodes[i].IsExist) { for(int j = 0;j < candidates.size();j++) { if(i + candidates[j] <= target) { valnodes[i+candidates[j]].IsExist = true; for(int k = 0;k < valnodes[i].set_v.size();k++) { vector<int>item_tmp; item_tmp.clear(); item_tmp = valnodes[i].set_v[k]; item_tmp.push_back(candidates[j]); if(!CheckIsExist(item_tmp,valnodes[i+candidates[j]].set_v)) valnodes[i+candidates[j]].set_v.push_back(item_tmp); } } } } } return valnodes[max].set_v; } };