首页 > 代码库 > LeetCode 39. Combination Sum (组合的和)
LeetCode 39. 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:
[ [7], [2, 2, 3] ]
题目标签:Array
题目给了我们一个candidates array 和一个 target, 让我们从array 里找到所有的组合,它的和是等于target的。任何组合只要是它的和等于target的话,都需要找到,但是不需要重复的。这道题中是可以重复利用一个数字的,那么我们就需要每次都代入同一个数字,直到它之和达到target 或者它超过了target, 然后在倒退回去一个数字,继续找下一个数字,这种情况肯定是要用递归了。这里是backtracking,每次倒退回一个数字,需要继续递归下去,在倒退,一直重复直到搜索了所有的可能性。
我们可以看原题中的例子:
[2,3,6,7] target 7
2 选2,sum = 2
2+2 选2,sum = 4
2+2+2 选2,sum = 6
2+2+2+2 选2,sum = 8 这时候 sum已经超出target,需要返回到上一个数字
2+2+2+3 选3,sum = 9, 也超出了target, 这里我们可以发现,如果是sorted array的话,从小到大,只要一次超出,后面的数字必然也会超出target,所以可以在第一次超出的时候就直接跳出这一个迭代
2+2+3 选3,sum = 7,等于target, 此时返回并且跳出这一个迭代,因为后面的数字肯定超出(array里不会有重复的数字)
2+3 选3,sum = 5,小于target,继续递归同一个数字
2+3+3 选3,sum = 8,超出target,返回上一个数字
2+6 选6,sum = 8,超出target,返回上一个数字
3 选3,这里继续从3开始递归
...
...
...
我们可以看出,一开始有一个迭代从2,一直到7,然后把每一个数字递归下去,包括它自己,每次递归下去的数字,会继续有一个迭代,一旦超出或者等于了,返回前面一个数字继续递归。所以把array sort一下就可以提早跳出那一轮的迭代。
具体看下面代码。
Java Solution:
Runtime beats 97.14%
完成日期:07/16/2017
关键词:Array
关键点:Backtracking with sorted array
1 public class Solution 2 { 3 public List<List<Integer>> combinationSum(int[] candidates, int target) 4 { 5 List<List<Integer>> list = new ArrayList<>(); 6 Arrays.sort(candidates); 7 backtrack(list, new ArrayList<>(), candidates, target, 0); 8 9 return list; 10 } 11 12 public static boolean backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int remain, int start) 13 { 14 if(remain < 0) // if remain is 0 or less than 0, meaning the rest numbers are even greater 15 return false; // therefore, no need to continue the loop, return false 16 else if(remain == 0) 17 { 18 list.add(new ArrayList<>(tempList)); 19 return false; 20 } 21 else 22 { 23 for(int i=start; i<nums.length; i++) 24 { 25 boolean flag; 26 tempList.add(nums[i]); 27 flag = backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can use same number. 28 tempList.remove(tempList.size() - 1); 29 30 if(!flag) // if find a sum or fail to find a sum, there is no need to continue 31 break;// because it is a sorted array with no duplicates, the rest numbers are even greater. 32 } 33 34 return true; // return true because previous tempList didn‘t find a sum or fail a sum 35 } 36 } 37 }
参考资料:
https://leetcode.com/problems/combination-sum/#/discuss
LeetCode 算法题目列表 - LeetCode Algorithms Questions List
LeetCode 39. Combination Sum (组合的和)