LeetCode 39 - Combination Sum

作者 QIFAN 日期 2017-01-14
LeetCode 39 - Combination Sum

原题链接: 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 是否小于两倍的最小值,若小于则直接断了这条路。如果不是继续走,这样子可以节省一些失败的空间。代码会稍微难看一点。