s= [2,3,6,7] and target 7
A solution set is :
[7]
[2,2,3]
repeated number is allowed
2. Implementation
Q1: From Combination Sum II, ?
A1: recursive + backtracking . add recursive call .remove
2.for (i; i < ; i ++)
.add(i)
helper(i)
.remove(size()-1)
return
1.Base Case
1-1 target == 0 return list of integers
1-2 target < 0 return
//1-3 i > len return
// NOTE: not len-1 since when i == len -1 we need to add
// no need for i > len since every time we call helper(i) with the same i which is bounded by the loop condition and never be greater than len
//NOTE: new ArrayList res.add( new ArrayList(item) );
// NOTE: like twoSum, threeSum need sorted Arrays.sort(candidates);
// NOTE: no duplicate start if ( i = 0 || candidates[i] != candidates[i-1]) {
// Time:O(n) over array, Space:O(n) list3. Similar Ones> public List
> combinationSum (int[] candidates, int target) { List
> res = new ArrayList
>(); // validate the input if ( candidates == null || candidates.length == 0 ) { return res; } // NOTE: like twoSum, threeSum need sorted Arrays.sort(candidates); helper(candidates, 0, target, new ArrayList
() ,res); return res; } private helper(int[] candidates, int start, int target, List item, List > res) { if ( target < 0) return; if (target == 0) { //NOTE: new ArrayList res.add( new ArrayList
(item) ); return; } for (int i = 0 ; i < candidates.length ; i++) { // NOTE: no duplicate start if ( i = 0 || candidates[i] != candidates[i-1]) { item.add(candidates[i]); helper(candidates, i, target - candidates[i], item, res); item.remove(item.size()-1); } } return; }
(M) Combination Sum II
(M) Combination Sum III
(M) Letter Combinations of a Phone Number
(M) Combinations
(M) Factor Combinations
No comments:
Post a Comment