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]
    ]

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

    组合时需要进行剪枝和去重
    去重使用used数组 i>index证明当前循环不是初始值 used[i-1]=0 且 candidates[i] == candidates[i-1] 表示i-1位置的值已经被使用过且不在本次循环中被使用 说明本次为重复选取相同值 应当去掉
    这种情况下如果used[i-1]不是0 则说明仍然处在同一个循环下 例: 1 1 6 取第二个1时会出现这种情况

    1. class Solution {
    2.     List<List<Integer>> res = new LinkedList<>();
    3.     LinkedList<Integer> list = new LinkedList<>();
    4.     int[] used;
    5.     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    6.         Arrays.sort(candidates);
    7.         used = new int[candidates.length];
    8.         findCombination(candidates, target, 0, 0);
    9.         return res;
    10.     }
    11.     public void findCombination(int[] candidates, int target, int sum, int index){
    13.         if(sum == target){
    14.             res.add(new LinkedList<>(list));
    15.             return;
    16.         }
    17.         for(int i = index;i < candidates.length && candidates[i] + sum <= target;i++){
    18.             if(i > index && used[i - 1] == 0 && candidates[i] == candidates[i-1])
    19.                 continue;
    20.             used[i] = 1;
    21.             list.add(candidates[i]);
    22.             findCombination(candidates, target, sum + candidates[i], i + 1);
    23.             list.removeLast();
    24.             used[i] = 0;
    25.         }
    26.     }
    27. }