Combinations

今天是一道有關(guān)遞歸的題目，來(lái)自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],
]

解題思路及代碼見(jiàn)閱讀原文

回復(fù)0000查看更多題目

解題思路

首先，先理解題意。該題從數(shù)學(xué)的角度比較容易理解，即n以內(nèi)數(shù)字的k的組合，即C(n,k)。我們要求的結(jié)果就是這個(gè)組合的所有可能。

然后，理解了題意下面就可以想解題思路，常用的思路有兩種：

• 第一種是基于數(shù)學(xué)公式的：C(n,k)=C(n-1,k-1)+C(n-1,k)?；谶@個(gè)公式即可寫(xiě)出相應(yīng)的遞歸代碼。公式的推導(dǎo)這里不詳述了，較為簡(jiǎn)單。

• 第二種是基于棧的思路，即每次向棧內(nèi)壓入一個(gè)數(shù)字，當(dāng)棧內(nèi)數(shù)字為k時(shí)，則此時(shí)即為一種可能。在計(jì)算下一組時(shí)，按照后進(jìn)先出的順序出棧，以此計(jì)算所有的可能性。

最后，我們來(lái)看代碼。

代碼如下

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)注我
該公眾號(hào)會(huì)每天推送常見(jiàn)面試題，包括解題思路是代碼，希望對(duì)找工作的同學(xué)有所幫助

image