Combinations
今天是一道有關(guān)遞歸的題目，來自LeetCode入热，難度為Medium拍棕，Acceptance為32.6%。
題目如下
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],
]
解題思路及代碼見閱讀原文
回復(fù)0000查看更多題目
解題思路
首先勺良，先理解題意绰播。該題從數(shù)學(xué)的角度比較容易理解，即n以內(nèi)數(shù)字的k的組合尚困，即C(n,k)蠢箩。我們要求的結(jié)果就是這個組合的所有可能。
然后事甜，理解了題意下面就可以想解題思路谬泌，常用的思路有兩種：
第一種是基于數(shù)學(xué)公式的：
C(n,k)=C(n-1,k-1)+C(n-1,k)÷咔基于這個公式即可寫出相應(yīng)的遞歸代碼掌实。公式的推導(dǎo)這里不詳述了，較為簡單邦马。第二種是基于棧的思路贱鼻，即每次向棧內(nèi)壓入一個數(shù)字，當(dāng)棧內(nèi)數(shù)字為k時滋将，則此時即為一種可能邻悬。在計算下一組時，按照后進先出的順序出棧随闽，以此計算所有的可能性父丰。
最后，我們來看代碼掘宪。
代碼如下
Java版
public class Solution {
/**
* @param n: Given the range of numbers
* @param k: Given the numbers of combinations
* @return: All the combinations of k numbers out of 1..n
*/
public static List<List<Integer>> combine(int n, int k) {
List<List<Integer>> combs = new ArrayList<List<Integer>>();
combine(combs, new ArrayList<Integer>(), 1, n, k);
return combs;
}
public static void combine(List<List<Integer>> combs, List<Integer> comb, int start, int n, int k) {
if(k==0) {
combs.add(new ArrayList<Integer>(comb));
return;
}
for(int i=start;i<=n;i++) {
comb.add(i);
combine(combs, comb, i+1, n, k-1);
comb.remove(comb.size()-1);
}
}
}
關(guān)注我
該公眾號會每天推送常見面試題蛾扇，包括解題思路是代碼攘烛，希望對找工作的同學(xué)有所幫助
image
