第 1 次循環，我們找出所有 1 個數的可能 [ 1 ]，[ 2 ]，[ 3 ]。4 和 5 不可能，解法一分析過了，因為總共需要 3 個數，4，5 全加上才 2 個數。

第 2 次循環，在每個 list 添加 1 個數， [ 1 ] 擴展為 [ 1 , 2 ]，[ 1 , 3 ]，[ 1 , 4 ]。[ 1 , 5 ] 不可能，因為 5 後邊沒有數字了。 [ 2 ] 擴展為 [ 2 , 3 ]，[ 2 , 4 ]。[ 3 ] 擴展為 [ 3 , 4 ]；

第 3 次循環，在每個 list 添加 1 個數， [ 1，2 ] 擴展為[ 1，2，3]， [ 1，2，4]， [ 1，2，5]；[ 1，3 ] 擴展為 [ 1，3，4]， [ 1，3，5]；[ 1，4 ] 擴展為 [ 1，4，5]；[ 2，3 ] 擴展為 [ 2，3，4]， [ 2，3，5]；[ 2，4 ] 擴展為 [ 2，4，5]；[ 3，4 ] 擴展為 [ 3，4，5]；

最後結果就是，[[ 1，2，3]， [ 1，2，4]， [ 1，2，5]，[ 1，3，4]， [ 1，3，5]， [ 1，4，5]， [ 2，3，4]， [ 2，3，5]，[ 2，4，5]， [ 3，4，5]]。

上邊分析很明顯了，三個循環，第一層循環是 1 到 k ，代表當前有多少個數。第二層循環就是遍歷之前的所有結果。第三次循環就是將當前結果擴展為多個。

public List<List<Integer>> combine(int n, int k) {
if (n == 0 || k == 0 || k > n) return Collections.emptyList();
List<List<Integer>> res = new ArrayList<List<Integer>>();
//個數為 1 的所有可能
for (int i = 1; i <= n + 1 - k; i++) res.add(Arrays.asList(i));
//第一層循環，從 2 到 k
for (int i = 2; i <= k; i++) {
List<List<Integer>> tmp = new ArrayList<List<Integer>>();
//第二層循環，遍歷之前所有的結果
for (List<Integer> list : res) {
//第三次循環，對每個結果進行擴展
//從最後一個元素加 1 開始，然後不是到 n ，而是和解法一的優化一樣
//(k - (i - 1） 代表當前已經有的個數，最後再加 1 是因為取了 n
for (int m = list.get(list.size() - 1) + 1; m <= n - (k - (i - 1)) + 1; m++) {
List<Integer> newList = new ArrayList<Integer>(list);
newList.add(m);
tmp.add(newList);
}
}
res = tmp;
}
return res;
}

解法四 遞歸

參考這裡。基於這個公式 C ( n, k ) = C ( n - 1, k - 1) + C ( n - 1, k ) 所用的思想，這個思想之前刷題也用過，但忘記是哪道了。

從 n 個數字選 k 個，我們把所有結果分為兩種，包含第 n 個數和不包含第 n 個數。這樣的話，就可以把問題轉換成

• 從 n - 1 裡邊選 k - 1 個，然後每個結果加上 n
• 從 n - 1 個裡邊直接選 k 個。

把上邊兩個的結果合起來就可以了。

public List<List<Integer>> combine(int n, int k) {
if (k == n || k == 0) {
List<Integer> row = new LinkedList<>();
for (int i = 1; i <= k; ++i) {
row.add(i);
}
return new LinkedList<>(Arrays.asList(row));
}
// n - 1 裡邊選 k - 1 個
List<List<Integer>> result = combine(n - 1, k - 1);
//每個結果加上 n
result.forEach(e -> e.add(n));
//把 n - 1 個選 k 個的結果也加入
result.addAll(combine(n - 1, k));
return result;
}

解法五 動態規劃

參考這裡，既然有了解法四的遞歸，那麼一定可以有動態規劃。遞歸就是壓棧壓棧壓棧，然後到了遞歸出口，開始出棧出棧出棧。而動態規劃一個好處就是省略了出棧的過程，我們直接從遞歸出口網上走。

public List<List<Integer>> combine(int n, int k) {
List<List<Integer>>[][] dp = new List[n + 1][k + 1];
//更新 k = 0 的所有情況
for (int i = 0; i <= n; i++) {
dp[i][0] = new ArrayList<>();
dp[i][0].add(new ArrayList<Integer>());
}
// i 從 1 到 n
for (int i = 1; i <= n; i++) {
// j 從 1 到 i 或者 k
for (int j = 1; j <= i && j <= k; j++) {
dp[i][j] = new ArrayList<>();
//判斷是否可以從 i - 1 裡邊選 j 個
if (i > j){
dp[i][j].addAll(dp[i - 1][j]);
}
//把 i - 1 裡邊選 j - 1 個的每個結果加上 i
for (List<Integer> list: dp[i - 1][j - 1]) {
List<Integer> tmpList = new ArrayList<>(list);
tmpList.add(i);
dp[i][j].add(tmpList);
}
}
}
return dp[n][k];
}

這裡遇到個神奇的問題，提一下，開始的的時候，最裡邊的 for 循環是這樣寫的

for (List<Integer> list: dp[i - 1][j - 1]) {
List<Integer> tmpList = new LinkedList<>(list);
tmpList.add(i);
dp[i][j].add(tmpList);
}

就是 List 用的 Linked，而不是 Array，看起來沒什麼大問題，在 leetcode 上竟然報了超時。看了下 java 的源碼。

//ArrayList
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//LinkedList
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

猜測原因可能是因為 linked 每次 add 的時候，都需要 new 一個節點對象，而我們進行了很多次 add，所以這裡造成了時間的耗費，導致了超時。所以刷題的時候還是優先用 ArrayList 吧。

接下來就是動態規劃的常規操作了，空間複雜度的優化，我們注意到更新 dp [ i ] [ * ] 的時候，只用到dp [ i - 1 ] [ * ] 的情況，所以我們可以只用一個一維數組就夠了。和72題解法二，以及5題，10題，53題等等優化思路一樣，這裡不詳細說了。

public List<List<Integer>> combine(int n, int k) {
List<List<Integer>>[] dp = new ArrayList[k + 1];
// i 從 1 到 n
dp[0] = new ArrayList<>();
dp[0].add(new ArrayList<Integer>());
for (int i = 1; i <= n; i++) {
// j 從 1 到 i 或者 k
List<List<Integer>> temp = new ArrayList<>(dp[0]);
for (int j = 1; j <= i && j <= k; j++) {
List<List<Integer>> last = temp;
if(dp[j]!=null){
temp = new ArrayList<>(dp[j]);
}
// 判斷是否可以從 i - 1 裡邊選 j 個
if (i <= j) {
dp[j] = new ArrayList<>();
}
// 把 i - 1 裡邊選 j - 1 個的每個結果加上 i
for (List<Integer> list : last) {
List<Integer> tmpList = new ArrayList<>(list);
tmpList.add(i);
dp[j].add(tmpList);
}
}
}
return dp[k];
}

總

開始的時候直接用了動態規劃，然後翻了一些 Discuss 感覺發現了新世界，把目前為止常用的思路都用到了，回溯，遞歸，迭代，動態規劃，這道題也太經典了！值得細細回味。