# 0040. Combination Sum II
###### tags: `Leetcode` `Medium` `backtracking` `DFS`
## 思路
每个dfs的意思相当于是在start及start后面找一个数加在currSum里面
所以要保证不能好几个start是不同index但指向同一个值即可
## Code

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        dfs(candidates, ans, new ArrayList<>(), 0, 0, target);
        return ans;
    }
    private void dfs(int[] candidates, List<List<Integer>> ans, List<Integer> curr, int start, int currSum, int target){
        if(currSum==target) ans.add(new ArrayList<>(curr));
        if(currSum>target || start==candidates.length) return;
        for(int i=start; i<candidates.length; i++){
            if(i>start && candidates[i]==candidates[i-1]) continue;
            curr.add(candidates[i]);
            dfs(candidates, ans, curr, i+1, currSum+candidates[i], target);
            curr.remove(curr.size()-1);
        }
    }
}