40 combination sum II

https://leetcode.com/problems/combination-sum-ii/submissions/

其实跟39也差不多，可以看作限制了每个数字使用次数的39，限制的次数就是数字出现的频率，所以这里先sort之后对每一段遍历一下加0-frequency个就行了

class Solution {
     List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, 0, new ArrayList<>(), target, 0);
        return ans;
    }
    private void dfs(int[] candidates, int index, List<Integer> path, int target, int sum) {
        if (sum > target) return;
        if (sum == target) {
            ans.add(new ArrayList<>(path));
            return;
        }
        if (index == candidates.length) {
            return;
        }
        int end = index + 1;
        while (end < candidates.length && candidates[end] == candidates[index]) end++;
        dfs(candidates, end, path, target, sum);
        int presize = path.size();
        for (int i = index; i < end; i++) {
            sum += candidates[index];
            path.add(candidates[index]);
            dfs(candidates, end, path, target, sum);
        }
        path.subList(presize, path.size()).clear();
    }
}