LeetCode 77 Combinations
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]]
對于permutation和combination這類題企孩，都可以使用backtracing遞歸或是dp畅哑。
思路一：backtracing
一開始的naive thinking是粹断，傳遞一個boolean數(shù)組記錄當前有哪些數(shù)已經(jīng)考慮過窜觉，然后每次調(diào)用dfs時將k-1怨喘。傳遞整個boolean空間會消耗過多的空間延塑，不妨只傳遞一個pointer羞福，在pointer之前的數(shù)所產(chǎn)生的combination都已經(jīng)考慮過逞敷。
代碼時注意兩點：
1）java中是指針賦值狂秦，因此如果要深度copy某個list（eg. ArrayList<Integer> comb），需要采用如下方式：
ArrayList<Integer> newComb = new ArrayList(comb);
2）對于每個回溯推捐，若combination還需要挑選k個數(shù)：
可以從start到n挑選k個
可以從start+1到n挑選k個
...
直到從n+1-k到n挑選k個（此時只有1種挑法）
再往后是不存在挑k個數(shù)的combination的裂问，因此該條件可以作為backtracing的剪枝條件。
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> combs = new ArrayList<>();
if (k <= 0 || k > n) return combs;
combs = combineRecursive(n, k, 1, new ArrayList<>(), combs);
return combs;
}
public List<List<Integer>> combineRecursive(int n, int k, int start, List<Integer> comb, List<List<Integer>> combs) {
if (k == 0) {
combs.add(new ArrayList(comb));
return combs;
}
for (int i = start; i <= n+1-k; i++) {
comb.add(i);
combs = combineRecursive(n, k-1, i+1, comb, combs);
comb.remove(comb.size()-1);
}
return combs;
}
}
思路二：dp
dp問題關鍵是找到遞推公式牛柒，對于combination存在如下遞推關系：
C(n,k) = C(n-1,k) + C(n-1,k-1)
即不取n的情況（此時還剩k個數(shù)要瓤安尽）和取n的情況（此時還剩k-1個數(shù)要取）皮壁。
從n=0,k=0的情況賦初值椭更。
代碼如下：
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>>[][] combs = new ArrayList[n+1][k+1];
for (int i = 0; i <= n; i++) {
combs[i][0] = new ArrayList<>();
combs[i][0].add(new ArrayList<>());
}
for (int j = 1; j <= k; j++) {
for (int i = j; i <= n-k+j; i++) {
combs[i][j] = new ArrayList<>();
if (i-j > 0) {
combs[i][j].addAll(combs[i-1][j]);
}
for (List tmp : combs[i-1][j-1]) {
List<Integer> tmpList = new ArrayList(tmp);
tmpList.add(i);
combs[i][j].add(tmpList);
}
}
}
return combs[n][k];
}
}
參考：
https://discuss.leetcode.com/topic/11718/backtracking-solution-java/8
