【LEETCODE】模拟面试-39. Combination Sum

helper(res, path, candidate, sum - candidate[i], i);

code区别： notice：需要sort if条件里 sum >= candidate[i]

Arrays.sort(candidate);    //需要sort

helper(res, path, candidate, sum, 0);     //参数多了sum

//每次path加入新元素后，sum减去元素：sum - candidate[i]

if ( sum == 0 )      //stop条件是sum被减为0了

for ( int i = position; i < candidate.length && sum >= candidate[i]; i++ )
//sum余额不足覆盖下一个i的话，就不用再走了，这就是sort的好处

https://leetcode.com/problems/combination-sum/

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is: [ , [2, 2, 3] ]

input: a candidate set, eg, [1, 2, 3, 6, 7], a target sum integer, eg, 4 output: find all possible unique combinations which can sum to be the target, and in each combination, the numbers can be repeated at unlimited times. eg, [2, 2] -> 4

We need a list of list to store result, and a list called path to store current single path. There is also a position to locate the starting point for every path.

Notice the sum target is able to decrease itself during the process.

For convenience, we will sort the candidate array first.

The starting position will iterate from 0 to candidate.length - 1

Since this question allows repeated numbers, for each path, we can do this repeated work by passing the same starting point i to next level, rather than i + 1.

So that, for each unique number, the path will firstly add it for unlimited times until return. Then remove this number one by one, to leave space for next number. Moreover, the next number will also repeatedly add itself first until return.

And every time if current sum is larger than current number, we can add the number to current path, and pass the remaining sum = current sum - current number to next level.

Until current sum is zero, we will add the path to final result list.

After each path has finished its trip and returns to upper level, we should remove the last number of current path, to accept other new numbers.

public class Solution {
public List<List<Integer>> combinationSum(int[] candidate, int sum){
List<List<Integer>> res = new ArrayList<List<Integer>>();
//corner

//core
List<Integer> path = new ArrayList<>();

Arrays.sort(candidate);

helper(res, path, candidate, sum, 0);       //start from position = 0

return res;
}

public void helper(List<List<Integer>> res, List<Integer> path, int[] candidate, int sum, int position){
//base
if ( sum == 0 ){
return ;
}

//current
for ( int i = position; i < candidate.length && sum >= candidate[i]; i++ ){
//next: pass down remaining 'sum', and afterwards 'start position'
helper(res, path, candidate, sum - candidate[i], i);
path.remove(path.size() - 1);
}

return ;
}
}

0 条评论

相关文章

8110

38070

66680

11620

Java常用集合源码级深度解析

Java集合工具包位于Java.util包下，包含了很多常用的数据结构，如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分：...

52860

14920

46060

HashSet和HashMap的区别 && HashTable和HashMap的区别

2.Hashtable 中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。

10330

字符串查找----R向单词查找树

13100 