Combinations
今天是一道有关递归的题目，来自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],
]
解题思路及代码见阅读原文
回复0000查看更多题目
解题思路
首先，先理解题意。该题从数学的角度比较容易理解，即n以内数字的k的组合，即C(n,k)。我们要求的结果就是这个组合的所有可能。
然后，理解了题意下面就可以想解题思路，常用的思路有两种：
第一种是基于数学公式的：
C(n,k)=C(n-1,k-1)+C(n-1,k)。基于这个公式即可写出相应的递归代码。公式的推导这里不详述了，较为简单。第二种是基于栈的思路，即每次向栈内压入一个数字，当栈内数字为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);
}
}
}
关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助
image
