153. 数字组合 II（DFS）

组合 II（DFS）"/>

153. 数字组合 II（DFS）

描述

给出一组候选数字(C)和目标数字(T),找出C中所有的组合，使组合中数字的和为T。C中每个数字在每个组合中只能使用一次。

• 所有的数字(包括目标数字)均为正整数。
• 元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。
• 解集不能包含重复的组合。 

您在真实的面试中是否遇到过这个题？  是

样例

给出一个例子，候选数字集合为[10,1,6,7,2,1,5] 和目标数字 8  ,

解集为：[[1,7],[1,2,5],[2,6],[1,1,6]]

分析：
这道题跟之前那道 Combination Sum 组合之和 本质没有区别，只需要改动一点点即可，之前那道题给定数组中的数字可以重复使用，而这道题不能重复使用，只需要在之前的基础上修改两个地方即可，首先在递归的for循环里加上if (i > start && num[i] == num[i - 1]) continue; 这样可以防止res中出现重复项，然后就在递归调用combinationSum2DFS里面的参数换成i+1，这样就不会重复使用数组中的数字了，代码如下：

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>> combinationSum2(vector<int> &num, int target) {// write your code herevector<int>out;vector<vector<int> >res;sort(num.begin(),num.end());combationSum2DFS(num,target,0,out,res);return res;}void combationSum2DFS(vector<int>&num,int target,int start,vector<int>&out,vector<vector<int> >&res){if(target<0)return;else if(target==0) res.push_back(out);elsefor(int i=start;i<num.size();i++){if(i>start&&num[i]==num[i-1]) continue;out.push_back(num[i]);combationSum2DFS(num,target-num[i],i+1,out,res);out.pop_back();}}
};