leetCode 77&39. Combinations & Combination Sum
原创leetCode 77&39. Combinations & Combination Sum
原创
77.Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Example:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]题目大意：在1 ... n 中任意选取k个数，将所有的情况罗列出来。
思路：这个就是典型的组合问题。同样是采用回溯算法。
解法：
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if (n <= 0||k<=0||k>n) return res;
combineHelper(n,k,res,1,new LinkedList<>());
return res;
}
public void combineHelper(int n, int k,List<List<Integer>> res,int start,LinkedList<Integer> resTemp){
if (resTemp.size() == k){
res.add(new LinkedList<>(resTemp));
return;
}
for(int i=start;i<=n;i++ ){
resTemp.addLast(i);
combineHelper(n,k,res,i+1,resTemp);
resTemp.removeLast();
}
}其实，我们可以对上面的算法进行一些优化，试想如果对于1,2,3,4,5,6,7,8这个序列中，查找长度为4的组合(n=8，k=4)，我们的start==6时，是否还能找到满足要求的序列呢？明显的不能，因为剩余的数字长度已经小于k了。
所以当 k-resTemp.size >n-i+1时候就不能找到了。所以for循环的执行条件为i <= n - k+ resTemp.size()+1。
于是：
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if (n <= 0||k<=0||k>n) return res;
combineHelper(n,k,res,1,new LinkedList<>());
return res;
}
public void combineHelper(int n, int k,List<List<Integer>> res,int start,LinkedList<Integer> resTemp){
if (resTemp.size() == k){
res.add(new LinkedList<>(resTemp));
return;
}
for(int i=start;i <= n - k+ resTemp.size()+1;i++ ){
resTemp.addLast(i);
combineHelper(n,k,res,i+1,resTemp);
resTemp.removeLast();
}
}从leetcode的提交结果上看，从原来的34ms提升到4ms，可见这一个优化是非常有效的。实际上这就是回溯算法常见的剪枝法，把不满足条件的提前排除掉。
39. Combination Sum
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
- All numbers (including
target) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]题目大意：在一个没有重复数字的数组中挑选数字，使其和等于target，一个数字可以取多次。
解法一：
思路：这实际上也是一个组合问题。
这个是我一开始的解法：for循环中的if是为了避免重复情况，比如[2,3,3]和[3,2,3],总是从当前的数字或者后面的数字中寻找，而不从前面的数字中寻找。
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
combinationSumHelper(candidates,target,res,new LinkedList<>());
return res;
}
public void combinationSumHelper(int[] candidates, int target,List<List<Integer>> res,LinkedList<Integer> tempRes){
if (target < 0) return;
if (0 == target){
res.add(new ArrayList<>(tempRes));
}
for (int i = 0;i<candidates.length;i++){
if (tempRes.isEmpty()){
tempRes.addLast(candidates[i]);
}else {
if(candidates[i]>=tempRes.getLast()){
tempRes.addLast(candidates[i]);
}else continue;
}
combinationSumHelper(candidates,target-candidates[i],res,tempRes);
tempRes.removeLast();
}
}解法二：
这里的start的使用非常的巧妙。
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
combinationSumHelper(candidates,target,res,new ArrayList<>(),0);
return res;
}
public void combinationSumHelper(int[] candidates, int target,List<List<Integer>> res,ArrayList<Integer> tempRes,int start){
if (target < 0) return;
if (0 == target){
res.add(new ArrayList<>(tempRes));
}
for (int i = start;i<candidates.length;i++){
tempRes.add(candidates[i]);
//这里的参数i就代替了解法一里面的if判断
combinationSumHelper(candidates,target-candidates[i],res,tempRes,i);
tempRes.remove(tempRes.size()-1);
}
}值得注意的是：回溯算法的退出条件。
总结：
组合问题的解法的整体思路与排列问题相似，但是排列问题的for是从0开始查询，而组合问题是从一个变量start开始查询的，因为start之前的已经处理过了，这样就避免重复。有关排列问题的回顾可以参考《LeetCode 46 & 47. Permutations I&II》。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。