回溯算法基礎(chǔ)總結(jié)

• 往往是遞歸中包含著回溯，所以回溯函數(shù)即遞歸函數(shù)
• 回溯的本質(zhì)是窮舉，窮舉所有可能，然后選出我們想要的答案
• 可以解決如下幾種問題

1. 組合問題：N個數(shù)里面按一定規(guī)則找出k個數(shù)的集合
2. 切割問題：一個字符串按一定規(guī)則有幾種切割方式
3. 子集問題：一個N個數(shù)的集合里有多少符合條件的子集
4. 排列問題：N個數(shù)按一定規(guī)則全排列，有幾種排列方式
5. 棋盤問題：N皇后，解數(shù)獨等等

• 回溯法解決的問題都可以抽象成樹型結(jié)構(gòu)
  因為回溯法解決的都是在集合中遞歸查找子集，集合的大小就構(gòu)成了樹的寬度，遞歸的深度，都構(gòu)成的樹的深度。
  遞歸就要有終止條件，所以必然是一棵高度有限的樹（N叉樹）
• 回溯算法模板

void backtracking(參數(shù)) {
    if (終止條件) {
        存放結(jié)果;
        return;
    }
    for (選擇：本層集合中元素（樹中節(jié)點孩子的數(shù)量就是集合的大小）) {
        處理節(jié)點;
        backtracking(路徑，選擇列表); // 遞歸
        回溯，撤銷處理結(jié)果
    }
}

77. 組合

思路

• 集合長度為n，所以外層循環(huán)n次

• 在循環(huán)中進(jìn)行遞歸操作，遞歸終止條件則是找到了滿足k大小的path數(shù)組

  
  
  image.png

var combine = function(n, k) {
    let result = []
    let path = []
    const backtracking = (n, k, startIndex) => {
        if (path.length === k) {
            result.push([...path])
            return
        }
        for (let i = startIndex; i <= n; i++) {
            path.push(i)
            backtracking(n, k, i+1)
            path.pop() // 回溯 撤銷處理的節(jié)點
        }
    }
    backtracking(n, k, 1)
    return result
};

剪枝優(yōu)化

• 如果for循環(huán)起始位置之后的元素個數(shù)已經(jīng)不滿足我們所需結(jié)果的長度，那么后面的元素就沒有必要再繼續(xù)循環(huán)了
• 已經(jīng)選擇的元素個數(shù)：path.length
• 結(jié)果還需要的元素個數(shù)： k - path.length
• for循環(huán)還需要遍歷的元素個數(shù)： n - i
• 需要滿足的條件：(n - i) >= (k - path.length)，即：i <= n - (k-path.length)
• 為什么需要+1，因為要包含起始位置也是可以的

var combine = function(n, k) {
    let result = []
    let path = []
    const backtracking = (n, k, startIndex) => {
        if (path.length === k) {
            result.push([...path])
            return
        }
        for (let i = startIndex; i <= n - (k - path.length()) + 1; i++) {
            path.push(i)
            backtracking(n, k, i+1)
            path.pop()
        }
    }
    backtracking(n, k, 1)
    return result
};