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個數(shù)的組合。 這個題我們給出2種解法 第一種：遞歸 對于任意的n和k， 1.我們先求出從1到n-1中任意k個數(shù)的組合 2.然后求，1到n-1中任意k-1個數(shù)的組合，每個組合加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%多，顯然遞歸要好一些。對此，我覺得可能是使用遞歸的過程中計算的都是我們需要求的組合，但是在回溯中會多次出現(xiàn)碰到“死胡同”這樣的情況，導致了2種解法在時間空間上存在差異。舉個例子： ?我們要求n=9,k=9的組合，顯然只有一種組合滿足題意，但是當我們使用回溯算法時，tempList分別加入1,2,3,4,5,6,7,8,9之后就不需要再計算了，但事實上，我們仍舊還計算了加入tempList中的第一個元素為2,3,4,5,6,7,8,9的情況，而這些情況顯然已經不符合題意了，我覺得這個過程做的無用功是導致這種解法不優(yōu)的原因。 既然如此，我們在原回溯解法上稍作優(yōu)化，在回溯方法的第一行加上一個判斷條件 if(tempList.size()+n-start+1 < k)return;假設之后所有元素都加入tempList中都比k小的時候，我們不需要再計算了。 這樣一來，運行結果在LeetCode上超越了85%左右，與遞歸解法相差小了很多； 由此可見，有時候一行代碼足以改變一種算法的優(yōu)劣程度

總結

以上是生活随笔為你收集整理的77. Combinations的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。