40 Combination Sum II

Leetcode

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:

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

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output:

[
[1,2,2],
[5]
]

---

与 39 题 Combination Sum 类似，区别是一个元素只能用一次。同样用递归求解。使用一个 list 记录生成树。由于一个元素只能用一次，先给数组排序，第 n 次递归的时候，如果使用过某个数，就在这一次递归中不再使用重复的数。

class Solution {
    List<List<Integer>> ret;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        ret=new ArrayList<>();
        ArrayList<Integer> list=new ArrayList<>();
        Arrays.sort(candidates);
        recur(candidates, list, target, 0);
        return ret;
    }
    
    private void recur(int[] can, List<Integer> list, int target, int index){
        if(target==0){
            ret.add(new ArrayList<>(list));
            return;
        }
        
        for(int i=index;i<can.length;++i){
            if(i>index && can[i]==can[i-1]) continue;
            if(target<can[i]) break;
            list.add(can[i]);
            recur(can,list,target-can[i],i+1);
            list.remove(list.size()-1);
        }
    }
}