原题链接: 39. Combination Sum
题干
给定一个不含重复元素的数组 nums 和一个目标值 target 。返回所有总和为 target 的组合(一个元素可以重复利用)。所有元素包括 target 都为正数。
举例
输入:nums = [2, 3, 6, 7], target = 7
输出:[[2,2,3], [7]]
思路
很常规的思路:先排序,然后从最小的元素开始列举。我用了一个递归,每次从范围内选择数:
- base case
- target == 0 。添加结果。
- 当范围内最小的数比 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++; if (target == 0) { res.add(e); return; } for (int i = lo; i <= hi; i++) { 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 是否小于两倍的最小值,若小于则直接断了这条路。如果不是继续走,这样子可以节省一些失败的空间。代码会稍微难看一点。