力扣 40 组合总和 II

题意：给定一个数组和一个target值，返回和为target且为给定数组子数组的所有结果，和上一题不同的是有重复元素

思路：深度优先搜索遍历每一种可能结果，思路和39题类似，唯一不同的是注意去除重复

思想：DFS

复杂度：时间O(n²)，空间O(n^2)

class Solution {
    List<List<Integer>> res = new ArrayList();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int len = candidates.length;
        if(len == 0)
            return res;
        Arrays.sort(candidates);
        build(candidates, target, new ArrayList<Integer>(), 0, 0);
        return res;
    }
    
    void build(int[] a, int target, List<Integer> temp, int index, int sum) {
        if(sum > target)
            return;
        if(sum == target) {
            res.add(new ArrayList(temp));
            return;
        }
        for(int i=index;i<a.length;i++) {
            // 去除重复的元素，
            if(i>index && a[i] == a[i-1])
                continue;
            temp.add(a[i]);
            build(a, target, temp, i+1, sum + a[i]);
            temp.remove(temp.size() - 1);
        }
    }
}