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