LeetCode题目：Combination Sum II

1. unique和erase的用法
`result.erase(unique(result.begin(),result.end()),result.end());`
2. 细心检查语法

Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

1432ms过大测试集合

```class Solution {
public:
vector > combinationSum2(vector &num, int target) {
if(num.size() == 0)
return vector >();
sort(num.begin(),num.end());
vector > > *pR = new vector > >(target + 1);
vector > > *pT = new vector > >(target + 1);
//initialize
{
int c0 = num[0];
if(c0 > 0 && c0 <= target)
{
vector titem = vector(1,c0);
(*pR)[c0].push_back(titem);
}
}

for(int k = 1; k < num.size(); ++k)
{
int ck = num[k];
for(int t = 1; t <= target; ++t)
{
(*pT)[t].clear();
vector > &excludePre = (*pR)[t];
for( int i = 0 ; i < excludePre.size(); ++i)
{
(*pT)[t].push_back(excludePre[i]);
}
if(t - ck > 0)
{
vector > &includePre = (*pR)[t - ck];
for( int i = 0 ; i < includePre.size(); ++i)
{
vector tResult = includePre[i];
tResult.push_back(ck);
(*pT)[t].push_back(tResult);
}
} else if (t == ck)
{
(*pT)[t].push_back(vector(1,ck));
}
}
vector > > *temp = pR;
pR = pT;
pT = temp;
}
vector > &result = (*pR)[target];
sort(result.begin(),result.end());
result.erase(unique(result.begin(),result.end()),result.end());
return result;
}
};
```

“LeetCode题目：Combination Sum II”上的2条回复

zp说：

class Solution {
public:
vector<vector > combinationSum2(vector &num, int target) {
sort(num.begin(), num.end());
vector<vector<vector > > dp;
for (int i = 0; i <= target; ++i) {
vector<vector > empty;
dp.push_back(empty);
}
for (int i = 0; i = 1; –k) {
if (k – x == 0) {
vector temp;
temp.push_back(x);
dp[k].push_back(temp);
} else if ((k – x > 0) && (!dp[k – x].empty())) {
for (int j = 0; j < dp[k – x].size(); ++j) {
vector temp = dp[k – x][j];
temp.push_back(x);
dp[k].push_back(temp);
}
}
}
}
vector<vector > result = dp[target];
sort(result.begin(),result.end());
result.erase(unique(result.begin(),result.end()),result.end());
return result;

}
};

lzj说：