理論基礎(chǔ)
回溯是和遞歸相輔相成的慰技，回溯的本質(zhì)就是暴力解法，用于那些多層for循環(huán)無法解決的問題组砚，比如組合吻商、切割、集合等糟红，回溯也有三個(gè)步驟
- 確定回溯函數(shù)的參數(shù)與返回值艾帐，一般情況下返回值為void乌叶，參數(shù)中一般有一個(gè)startIndex
- 確定終止條件
- 單層邏輯，一般是for循環(huán)里帶遞歸柒爸，并且要有回溯
77. 組合
77. 組合 - 力扣（LeetCode）
組合是典型的遞歸問題准浴，參見遞歸的三步驟
class Solution {
public List<List<Integer>> result = new ArrayList<>();
public List<Integer> path = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
public void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
//不能直接add path，因?yàn)閜ath后面還會(huì)改變捎稚，所以要新建一個(gè)
result.add(new ArrayList<>(path));
return;
}
for (int i=startIndex; i<=n; i++) {
path.add(i);
backtracking(n, k, i+1);
//回溯乐横，將最后一個(gè)移除
path.removeLast();
}
}
}
對(duì)于本題還可以再優(yōu)化，這里for循環(huán)里i是從startIndex到n今野，但實(shí)際情況是不需要到n晰奖，只需要到n-(k-path.size())+1
