【LeetCode】【算法】39.组合总和

LeetCode 39.组合总和

题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

思路

思路：经典回溯问题，同时做剪枝

上面这张图就能够看明白了：

1. 对数组做排序（便于后面剪枝）
2. 从candidates数组中取数，每取一个数，后面仍有candidates.length种取法，因为可以重复取。取数的过程中，做剪枝：if (sum+candidates[i]>target) break，如果加上当前候选和超出target则直接break，不需要再做后面的加法（再次印证了为什么要做排序）
3. 如果没有超出target，则将candidates[i]加入到path中，并进行下一层的递归，递归结束后移除加入到path中的candidates[i]元素
4. 值得注意的是，递归时backTracking(res, path, candidates, target, sum + candidates[i], i);，最后一位起始索引为i，说明第i位是可以被无限制重复选取的（只要每次加上不超过target就可以无限选）

代码

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 组合，回溯，剪枝
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        backTracking(result, new ArrayList<>(), candidates, target, 0, 0);
        return result;
    }

    public void backTracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
        // res -> 结果集
        // path -> 当前路径
        // candidates -> 候选数字
        // target -> 目标和
        // sum -> 当前和
        // idx -> 允许选取的下标起始位置
        if (sum == target) { // 说明找到了结果
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            backTracking(res, path, candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1); // 回溯，移除path的最后一个元素
        }

    }
}

原文地址：https://blog.csdn.net/passer__jw767/article/details/143675127

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！