理論基礎(chǔ)

回溯是和遞歸相輔相成的，回溯的本質(zhì)就是暴力解法，用于那些多層for循環(huán)無法解決的問題，比如組合、切割、集合等，回溯也有三個步驟

1. 確定回溯函數(shù)的參數(shù)與返回值，一般情況下返回值為void，參數(shù)中一般有一個startIndex
2. 確定終止條件
3. 單層邏輯，一般是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，因為path后面還會改變，所以要新建一個
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i=startIndex; i<=n; i++) {
            path.add(i);
            backtracking(n, k, i+1);
            //回溯，將最后一個移除
            path.removeLast();
        }
    }
}

對于本題還可以再優(yōu)化，這里for循環(huán)里i是從startIndex到n，但實際情況是不需要到n，只需要到n-(k-path.size())+1