77. 組合
class Solution {
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> value = new ArrayList<>();
backtracking(n, k, 1);
return result;
}
private void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.add(new ArrayList<>(path));
return;
}
// if n = k = 4. 那么蹭睡，只有1，2赶么，3肩豁，4滿足需求，后面從2開(kāi)始的都不滿足辫呻，說(shuō)明for循環(huán)中n的值可以根據(jù)需要來(lái)進(jìn)行縮減
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
path.add(i);
backtracking(n, k, i + 1);
path.removeLast();
}
}
}
回溯清钥，回溯算法使用同一個(gè)模板，關(guān)鍵是做的題多放闺，自然就寫(xiě)出來(lái)了祟昭，如果剛學(xué)回溯不要擔(dān)憂很困難。
寫(xiě)個(gè)一周怖侦，自然就懂怎么寫(xiě)回溯了篡悟。
剪枝是寫(xiě)完回溯再去分析的問(wèn)題，不用在寫(xiě)的過(guò)程反復(fù)去推敲匾寝，反而啥都寫(xiě)不好搬葬。先寫(xiě)出來(lái)，在優(yōu)化艳悔。
剪枝：
該題目的剪枝操作急凰，當(dāng)長(zhǎng)度小于了約定的個(gè)數(shù)，就無(wú)法再找到新的排列組合了猜年。比如抡锈，n=3,k=4,那么一個(gè)都沒(méi)有
216. 組合總和 III
class Solution {
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> result = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
// 從[1,9]之間選取k個(gè)數(shù)疾忍，相加得到n
backtracking(k, n, 1);
return result;
}
private void backtracking(int k, int n, int startIndex) {
if (path.size() == k) {
if (n == 0) {
result.add(new LinkedList<>(path));
}
return;
}
// 從1開(kāi)始
for (int i = startIndex; i <= 9; i++) {
path.add(i);
backtracking(k, n - i, i + 1);
path.removeLast();
}
}
}
未剪枝代碼如上所示，那么剪枝呢企孩？
因?yàn)槭窃赱1,9]之間選取數(shù)字锭碳，那么每一個(gè)數(shù)字是不相同的。
如果k=2勿璃，n=4擒抛，假設(shè)n1 = 2, n2 = 3，發(fā)現(xiàn)sum = n1 + n2 >= n, 那么后面的數(shù)還有遍歷的必要么补疑？
private boolean backtracking(int k, int n, int startIndex) {
if (path.size() == k) {
if (n == 0) {
result.add(new LinkedList<>(path));
}
return n <= 0;
}
// 從1開(kāi)始
for (int i = startIndex; i <= 9; i++) {
path.add(i);
boolean backtracking = backtracking(k, n - i, i + 1);
path.removeLast(); // 位置放在上面來(lái)了歧沪，因?yàn)橐旬?dāng)前層級(jí)放入的先移除再判斷
if (backtracking) {
return !backtracking; // 上一級(jí)還是需要正常遍歷的
}
// path.removeLast();
}
return false;
}
再思考一下，如果一個(gè)元素莲组，進(jìn)去就比期望的元素大诊胞，那么還有必要向后面查找么？
比如想查找n=4锹杈，k=2,結(jié)果n1 = 4.
private boolean backtracking(int k, int n, int count, int startIndex) {
if (startIndex > n) { // 不能設(shè)置等于撵孤，如果k=1,就掛了
return true;
}
if (path.size() == k) {
if (count == 0) {
result.add(new LinkedList<>(path));
}
return count <= 0;
}
// 從1開(kāi)始
for (int i = startIndex; i <= 9; i++) {
path.add(i);
boolean backtracking = backtracking(k, n, count - i, i + 1);
path.removeLast(); // 位置放在上面來(lái)了，因?yàn)橐旬?dāng)前層級(jí)放入的先移除再判斷
if (backtracking) {
return !backtracking; // 上一級(jí)還是需要正常遍歷的
}
// path.removeLast();
}
return false;
}
但在leecode上竭望，發(fā)現(xiàn)這個(gè)算法的時(shí)間居然比上一個(gè)慢邪码，只能說(shuō)明測(cè)試用例和復(fù)雜度并不強(qiáng)。
畢竟這只是一個(gè)10以?xún)?nèi)的加法咬清，最大值為55.
17. 電話號(hào)碼的字母組合
private String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
private List<String> result = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return result;
}
backtracking(digits, 0, new StringBuilder());
return result;
}
private void backtracking(String digits, int startIndex, StringBuilder path) {
if (path.length() == digits.length()) {
result.add(path.toString());
return;
}
String str = numString[digits.charAt(startIndex) - '0'];
for (int i = 0; i < str.length(); i++) {
path.append(str.charAt(i));
backtracking(digits, startIndex + 1, path);
path.deleteCharAt(path.length() - 1);
}
}
問(wèn)題并不難闭专，有一個(gè)難點(diǎn)在字符數(shù)字轉(zhuǎn)為數(shù)字。
如果使用int去接收旧烧，它不會(huì)轉(zhuǎn)為char類(lèi)型對(duì)應(yīng)的數(shù)字影钉，而是ascll編碼表對(duì)應(yīng)的數(shù)字
