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,可见这一个优化是非常有效的。实际上这就是回溯算法常见的剪枝法,把不满足条件的提前排除掉。
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:
target
) will be positive integers.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 删除。