題目：給出一組候選數(shù)字(C)和目標(biāo)數(shù)字(T),找出C中所有的組合庶艾，使組合中數(shù)字的和為T闯参。C中每個(gè)數(shù)字在每個(gè)組合中只能使用一次
類型：回溯
地址：http://www.lintcode.com/zh-cn/problem/combination-sum-ii/
注意事項(xiàng)
- 所有的數(shù)字(包括目標(biāo)數(shù)字)均為正整數(shù)倔丈。
- 元素組合(a1, a2, … , ak)必須是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)渊抄。
- 解集不能包含重復(fù)的組合势誊。
代碼實(shí)現(xiàn)：
class Solution {
public:
/**
* @param num: Given the candidate numbers
* @param target: Given the target number
* @return: All the combinations that sum to target
*/
vector<vector<int> > result;
vector<int> tmp;
void combinationSum(vector<int> &num, int target)
{
// 當(dāng)沒有元素或目標(biāo)和為負(fù)或0時(shí)，終止（因?yàn)樗性貫檎麛?shù)）
if(num.size() == 0 || target <= 0) //注意剪枝
return;
//找到一組解
if(num[0] == target)
{
tmp.push_back(num[0]);
result.push_back(tmp);
tmp.pop_back();
}
vector<int> B;
B.assign(num.begin()+1, num.end());
tmp.push_back(num[0]);
combinationSum(B, target-num[0]);
tmp.pop_back();
combinationSum(B, target);
}
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
// write your code here
sort(num.begin(), num.end());
combinationSum(num, target);
// 刪除重復(fù)元素
sort(result.begin(), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
return result;
}
};
