offer2-82

给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        Set<List<Integer>> result = new HashSet<>();
        List<Integer> curRes = new ArrayList<>();
        combine(result, curRes, 0, 0, candidates, target);
        return new ArrayList<>(result);
    }

    void combine(Set<List<Integer>> result, List<Integer> curRes, int index, int curSum, int[] candidates, int target) {
        if (curSum == target) {
            List<Integer> one = new ArrayList<>(curRes);
            result.add(one);
            return;
        } else if (curSum > target || index >= candidates.length) {
            return;
        }

        curRes.add(candidates[index]);
        combine(result, curRes, index + 1, curSum + candidates[index], candidates, target);
        curRes.remove(curRes.size() - 1);
        combine(result, curRes, index + 1, curSum, candidates, target);
    }
}
//leetcode submit region end(Prohibit modification and deletion)