Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
For example,
If n = 4 and k = 2, a solution is:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
题意:给定n和k,求1-n中任意k个数的组合。
这个题我们给出2种解法
第一种:递归
对于任意的n和k,
1.我们先求出从1到n-1中任意k个数的组合
2.然后求,1到n-1中任意k-1个数的组合,每个组合加n,
最后将组合合并到一个集合即可
具体代码:
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> list = new ArrayList<>();
if(n<k)
return list;
if(n==k){
List<Integer> list1 = new ArrayList<>();
for(int i=1;i<=n;i++)
list1.add(i);
list.add(list1);
return list;
}
if(k == 1){
for(int i=0;i<n;i++){
List<Integer> list1 = new ArrayList<>();
list1.add(i+1);
list.add(list1);
}
return list;
}
List<List<Integer>> list2 = combine(n-1,k-1);
for(List<Integer> l : list2){
l.add(n);
}
list = combine(n-1,k);
list.addAll(list2);
return list;
}
}
第二种解法,我们使用回溯的思想
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> list = new ArrayList<>();
if(n<k)
return list;
combine(list,new ArrayList<Integer>(),k,n,1);
return list;
}
public void combine(List<List<Integer>> list,List<Integer> tempList,int k,int n,int start){
if(tempList.size() == k){
list.add(new ArrayList<Integer>(tempList));
}else{
for(int i=start;i<=n;i++){
tempList.add(i);
combine(list,tempList,k,n,i+1);
tempList.remove(tempList.size()-1);
}
}
}
}
上述2种解法中,递归解法在LeetCode上超越了90%左右,而使用回溯的解法只超越了40%多,显然递归要好一些。对此,我觉得可能是使用递归的过程中计算的都是我们需要求的组合,但是在回溯中会多次出现碰到“死胡同”这样的情况,导致了2种解法在时间空间上存在差异。举个例子:
我们要求n=9,k=9的组合,显然只有一种组合满足题意,但是当我们使用回溯算法时,tempList分别加入1,2,3,4,5,6,7,8,9之后就不需要再计算了,但事实上,我们仍旧还计算了加入tempList中的第一个元素为2,3,4,5,6,7,8,9的情况,而这些情况显然已经不符合题意了,我觉得这个过程做的无用功是导致这种解法不优的原因。
既然如此,我们在原回溯解法上稍作优化,在回溯方法的第一行加上一个判断条件
if(tempList.size()+n-start+1 < k)
return;
假设之后所有元素都加入tempList中都比k小的时候,我们不需要再计算了。
这样一来,运行结果在LeetCode上超越了85%左右,与递归解法相差小了很多;
由此可见,有时候一行代码足以改变一种算法的优劣程度
今天的文章77. Combinations分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/33607.html