struct Node
{
int key;
int cnt;
};
class Solution {
private:
vector<Node> v;
vector<Node> data;
vector<vector<
int> > result;
int len;
void generate(
int vdep,
int index,
int target)
{
if(target<
0)
return;
if(target==
0)
{
vector<
int> re;
for(
int i=
0;i<vdep;i++)
for(
int j=
0;j<v[i].cnt;j++)
re.push_back(v[i].key);
result.push_back(re);
return;
}
for(
int i=index;i<len;i++)
{
for(
int j=
1;j<=data[i].cnt;j++)
{
v[vdep].key=data[i].key;
v[vdep].cnt=j;
generate(vdep+
1,i+
1,target-v[vdep].key*j);
}
}
}
public:
vector<vector<
int> > combinationSum2(vector<
int> &num,
int target)
{
sort(num.begin(),num.end());
//group
int old=
0;
Node node;
for(
int i=
0;i<num.size();i++)
{
if(num[i]==old) data[data.size()-
1].cnt++;
else {
node.key=num[i];
old=node.key;
node.cnt=
1;
data.push_back(node);
}
}
for(
int i=
0;i<num.size();i++)
v.push_back(node);
result.clear();
len=data.size();
generate(
0,
0,target);
return result;
}
};