[Leetcode]Combination Sum II
//本題還是有點疑惑...
//和combination sum一樣，dfs
//但是因為此時是不可以重復利用，但是如果存在兩個1的話按照例子就可以重復用同樣的數值，只是不可多次使用
//Book上說用pre來判斷，但是這樣難道不會miss例子中的1，1，6的情況？...
//有或者dfs的函數就是按照各個subject出現次數而運行的...要想想...
class Solution {
public:
vector
> combinationSum2(vector &num, int target) {
int len=num.size();
vector> result;
vector temp;
sort(num.begin(),num.end());
dfs(num,target,0,temp,result);
return result;
}
void dfs(vector&num, int gap, int start, vector&temp, vector>&result)
{
if(gap==0)
{
//if(result.find(temp)==result.end())//其實說這麼多就是這麼個意思，可是明顯vector>裡面沒有對應的find函數，編譯報錯
result.push_back(temp);
return;
}
int pre=-1;
for(int i=start;i
if(gap
if(pre==num[i])continue;
pre=num[i];
temp.push_back(num[i]);
dfs(num,gap-num[i],i+1,temp,result);
temp.pop_back();
}
}
};
