40. Combination Sum II

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.

由于有重复性元素，因此先将数组排序。
储存一个数组，记录元素是否被选择。
回溯，遍历选择元素，并计算加和，并记录选择的元素。当选择的元素与上一个元素重复时，则跳过。

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(candidates, ret, new ArrayList<>(), new int[candidates.length], target, 0, 0);
        return ret;
    }
    
    private void backtracking(int[] candidates, List<List<Integer>> ret, List<Integer> arr, int[] visited, int target, int sum, int level){
        if(sum > target ){
            return;
        }
        else if (sum == target){
            ret.add(new ArrayList<>(arr));
            return;
        }

        for(int i = level; i < candidates.length; i++){
            if(i > 0 && candidates[i] == candidates[i-1] && visited[i-1] == 0) continue;
            visited[i] = 1;
            arr.add(candidates[i]);
            sum+= candidates[i];
            backtracking(candidates, ret, arr, visited, target, sum, i+1);
            visited[i] = 0;
            sum-= candidates[i];
            arr.remove(arr.size()-1);
        }
    }
}