題目
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Example:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
解法思路（一）
- 組合；
- 回溯；
- 相當于求 C 24长赞；
- 注意組合和排列的區(qū)別氧急，對排列來說，[1, 2] 和 [2, 1] 是不同的排列剃根，對組合來說是同一個組合；
- 當輸入給出時，一棵樹就形成了物遇，比如輸入：
4, 2，形成的樹如下：
算法過程.png
- 問題轉(zhuǎn)化為求這棵樹長度為 2 的路徑；
解法實現(xiàn)（一）
時間復雜度
- O(n^k)询兴；
空間復雜度
- O(k)乃沙；
關(guān)鍵字
遞歸 回溯 樹 長度為 k 的路徑數(shù) 深復制
實現(xiàn)細節(jié)
-
start控制當前層可以納入組合的邊從第幾位開始； - 下一層可用來納入組合的邊诗舰，只能從當前邊的右邊剩余的邊中找警儒，
i是當前邊，i + 1是當前邊的右邊眶根；
package leetcode._77;
import java.util.LinkedList;
import java.util.List;
public class Solution77_1 {
private LinkedList<List<Integer>> res;
public List<List<Integer>> combine(int n, int k) {
res = new LinkedList<>();
if (n <= 0 || k <= 0 || k > n) {
return res;
}
LinkedList<Integer> c = new LinkedList<>();
findCombination(n, k, 1, c);
return res;
}
private void findCombination(int n, int k, int start, LinkedList<Integer> c) {
if (c.size() == k) {
res.addLast((List<Integer>)c.clone());
return;
}
for (int i = start; i <= n; i++) {
c.addLast(i);
findCombination(n, k, i + 1, c);
c.removeLast();
}
return;
}
}
解法思路（二）
剪枝
- 不可能得到解的路徑就不去遍歷了蜀铲，相當于把這樣的路徑從樹中剪掉，所謂剪枝属百；
結(jié)論
- 循環(huán)中蝙茶，
i不一定非要走到最右端n，走到n - (k - c.size) + 1就可以了诸老；
推導過程
-
k是遞歸的深度隆夯，也是組合要求的長度； -
c.size()是在找長度為k的組合的過程中别伏，已經(jīng)找到了多少個元素蹄衷； -
k - c.size是還要找到幾個元素才能找出一個有k個元素的組合； - 拿 C24 來說厘肮，看第一層愧口，要找到一個 2 個元素的組合，就是在第一層找一個元素类茂，然后在第二層耍属，從剩余的元素中找再找一個元素，相當于在第一層中找倆元素巩检；
- 而且找的規(guī)則是這樣的：如果第一個元素找的是第
i個元素厚骗，那么第二個元素最左得從i + 1找； - 那么保證能取出兩個元素的
i的最右端在哪呢兢哭？ -
4 - (2 - 0)距最右邊界隔著倆元素领舰，再右移一位4 - (2 - 0) + 1，距最右隔一個位置迟螺，加上這個位置本身一共可以填2個元素冲秽，這個位置就是保證能取出兩個元素的i的最右的位置； -
(2 - 0)是(k - c.size)矩父； -
4是n锉桑； - 這個位置一般化就是：
n - (k - c.size) + 1； -
n - (k - c.size) + 1是小于等于n的窍株，進而達到剪枝的目的民轴，進而達到了優(yōu)化性能的目的攻柠；
解法實現(xiàn)（二）
時間復雜度
- O(n^k)；
空間復雜度
- O(k)杉武；
關(guān)鍵字
樹 剪枝 遞歸 回溯
實現(xiàn)細節(jié)
- 只把
n變成了n - (k - c.size) + 1辙诞；
package leetcode._77;
import java.util.LinkedList;
import java.util.List;
public class Solution77_2 {
private LinkedList<List<Integer>> res;
public List<List<Integer>> combine(int n, int k) {
res = new LinkedList<>();
if (n <= 0 || k <= 0 || k > n) {
return res;
}
LinkedList<Integer> c = new LinkedList<>();
findCombination(n, k, 1, c);
return res;
}
private void findCombination(int n, int k, int start, LinkedList<Integer> c) {
if (c.size() == k) {
res.addLast((List<Integer>)c.clone());
return;
}
for (int i = start; i <= n - (k - c.size()) + 1; i++) {
c.addLast(i);
findCombination(n, k, i + 1, c);
c.removeLast();
}
return;
}
}
