LeetCode——组合总和II

NO.40 组合总和 II 中等

本题和徒手挖地球十二周目中组合总和的思路一样只是少量变化，区别在于本题candidate数组中的元素不能重复使用(只能使用一次)，本题数组中有重复元素。

思路一：深度优先遍历，回溯法 从39题组合总和的基础上进行分析改进：

1. 本题数组中的每个元素不能重复使用，但是数组中存在重复元素(每个相等元素都可以使用一次)
2. 每个节点的孩子应该使用下一个元素开始，即不再是index而是index+1；
3. 本题数组中存在重复元素，所以仅仅采用”每个孩子从下一个元素(index+1)开始”是不够的，因为index之后的元素依然可能重复，因此我们不能让相等元素不能作为兄弟节点，但是可以作为父子。根据这个发现，我们可以先将candidates排序，然后每次搜索时如果本节点和前面的兄弟节点相等，则剪枝。

List<List<Integer>> res=new ArrayList<>();
int[] candidates;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    if (candidates==null)return res;
    this.candidates=candidates;
    //排序，将重复元素紧凑在一起
    Arrays.sort(candidates);
    dfs(target,0,new LinkedList<Integer>());
    return res;
}

private void dfs(int target, int index, LinkedList<Integer> ans) {
    //说明找到符合要求的路径
    if (target==0){
        res.add(new ArrayList<>(ans));
        return;
    }
    for (int i=index;i<candidates.length;i++){
        //本节点和前面的兄弟节点相等,则小剪枝，跳过这条路径
        if (i > index && candidates[i] == candidates[i - 1]) {
            continue;
        }
        //如果减数大于目标值则差为负数，不符合结果，且后续元素都大于目标值，大剪枝，结束后序搜索
        if (target<candidates[i]) {
            break;
        }
        ans.add(candidates[i]);
        //不能重复使用同一元素，所以下次搜索起点从index+1开始
        dfs(target-candidates[i],i+1,ans);
        //每次回溯移除最后一次添加的元素
        ans.removeLast();
    }
}

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github