LeetCode 39 - Combination Sum

题干

给定一个不含重复元素的数组 nums 和一个目标值 target 。返回所有总和为 target 的组合（一个元素可以重复利用）。所有元素包括 target 都为正数。

举例
输入：nums = [2, 3, 6, 7], target = 7
输出：[[2,2,3], [7]]

思路

很常规的思路：先排序，然后从最小的元素开始列举。我用了一个递归，每次从范围内选择数：

base case
1. target == 0 。添加结果。
2. 当范围内最小的数比 target 大，那就返回。
一般情况
- 将当前数字加入，target 减小进入下一轮递归

代码：

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(candidates);
    Integer count = new Integer();
    combinationSum(res, candidates, target, 0, candidates.length - 1, new ArrayList<>(), count);
    System.out.println(count);
    return res;
}
private void combinationSum(List<List<Integer>> res, int[] nums, int target, int lo, int hi, List<Integer> e, Integer count) {
    count++;
    // base case
    if (target == 0) {
        res.add(e);
        return;
    }
    for (int i = lo; i <= hi; i++) {
        // base case
        if (nums[i] > target) {
            e = null;
            return;
        }
        List<Integer> newE = new ArrayList<>();
        newE.addAll(e);
        newE.add(nums[i]);
        combinationSum(res, nums, target - nums[i], i, hi, newE);
    }
}

Can we do better?

在递归时，可以判断 target 是否小于两倍的最小值，若小于则直接断了这条路。如果不是继续走，这样子可以节省一些失败的空间。代码会稍微难看一点。

题干
思路

LeetCode 39 - Combination Sum

题干

思路

FEATURED TAGS

FRIENDS