40.Combination Sum II

https://leetcode.com/problems/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 target8,

A solution set is:

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

2.Code

这道题跟之前那道Combination Sum 组合之和本质没有区别，只需要改动一点点即可，之前那道题给定数组中的数字可以重复使用，而这道题不能重复使用，只需要在之前的基础上修改两个地方即可，首先在递归的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);
        }
    }