# 40.Combination Sum II

## 1.Description(Medium)

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.

### Notice

* 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.

**Example**

Given candidate set`[10,1,6,7,2,1,5]`and target`8`,

A solution set is:

```
[
  [1,7],
  [1,2,5],
  [2,6],
  [1,1,6]
]
```

## 2.Code

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

```
public List<List<Integer>> combinationSum2(int[] num, int target) {
        List<List<Integer>> result=new ArrayList<>();
        if(num==null || num.length==0){
            return result;
        }
        List<Integer> path=new ArrayList<Integer>();
        Arrays.sort(num);
        dfs(num,0,target,path,result);
        return result;
    }

    public void dfs(int[] num,int startindex,int target,List<Integer> path,List<List<Integer>> result){
        if(target==0){
            result.add(new ArrayList<Integer>(path));
        }
        for(int i=startindex;i<num.length;i++){
            //这里必须先判断i不是startindex,否则会出现ArrayIndexOutOfBoundsException
            if(i!=startindex && num[i]==num[i-1]){
                continue;
            }
            if(target<num[i]){
                break;
            }
            path.add(num[i]);
            //这里要从i+1
            dfs(num,i+1,target-num[i],path,result);
            path.remove(path.size()-1);
        }
    }
```