回溯算法可以形象地理解為在一棵n 叉樹上的探索過程，其核心機制就是"開枝散葉"與"修剪枝條"的有機結合

理解回溯：以 Leetcode 93 題"復原 IP 地址"為例：

🌿 開枝過程

• 每個 IP 段的長度範圍為 [1, 3]，因此每層循環最多擴展3 個分支

• 這相當於在樹的每個節點處，橫向展開1-3 條可能的路徑

  🍃 散葉過程

• 選中一個有效分支後，縱向深入遞歸探索
• IP 地址需要 4 個段（被 3 個"."分割），因此需要遞歸 4 層
• 這個過程如同枝葉從主幹不斷向外蔓延生長

剪枝：智慧的"修剪藝術"

回溯中的剪枝，本質上是"砍掉 n 叉樹中無效枝條"的優化策略。面對大規模問題和深層遞歸時，及時識別並剪除不可能的分支至關重要

剪枝的四重境界

1. 整樹剪枝：問題本身無解，根本不開始搜索
2. 子樹剪枝：當前節點的所有子孫都不可能，整體放棄
3. 分支剪枝：當前分支的所有延伸都無效，終止該分支
4. 路徑剪枝：當前路徑已違反約束，立即回溯

剪枝的哲學

剪枝如同睿智的園丁：在枝條初生時便預判其未來——若不能開花結果，就及時剪除，避免浪費寶貴的養分（計算資源）。
這種"開枝散葉尋可能，修剪枝條保效率"的思維，正是回溯算法的精髓所在

舉個例子

版本1:

var restoreIpAddresses = function(s) {
        let length = s.length, result = [], path = []

        // 判斷字符串 string 在範圍 [startIndex, endIndex] 區間內的字符串是否是有效的 IP 地址段
        const isValidate = (string, startIndex, endIndex) => {
            let ipTextLength = endIndex - startIndex + 1

            /* 
            非法 IP 地址段的特點：
            1. 長度大於3
            2. 如果首位是 '1'，且長度不為1
            3. 轉換為數字後，不在 [0, 255] 區間
            */
            if (ipTextLength > 3) return false
            if (string[startIndex] === '0' && ipTextLength !== 1) return false
            let text = string.substring(startIndex, endIndex + 1)
            if (Number(text) > 255 || Number(text) < 0) return false
            return true
        }

        const backtrace = (startIndex) => {
            // 收集結果
            if (path.length >= 4 || startIndex >= length ) {
                if (startIndex === length && path.length === 4) result.push(path.join('.'))
                return 
            }

            for (let i = startIndex; i < length; i++) {
                if (isValidate(s, startIndex, i) === true) {
                    path.push(s.substring(startIndex, i + 1))
                    backtrace(i + 1)
                    path.pop()
                }
            }
        }
        
        backtrace(0)
        return result
    };

版本2:

var restoreIpAddresses = function(s) {
        let result = []

        // 第1點：題目中只説明 s 長度為：1 <= s.length <= 20，並不一定符合有效 IP 段。所以要做檢測
        if (s.length < 4 || s.length > 12) return result

        const isValidate = (testString, startIndex, endIndex) => {
            //1. 非法的情況：轉換為數字，不在 [0, 255] 區間內；2. 長度大於1的情況下，首位是0；
            const length = endIndex - startIndex + 1
            if (length > 1 && testString[startIndex] === '0') return false

            const num = testString.substring(startIndex, endIndex + 1)
            if (Number(num) > 255 || Number(num) < 0) return false
            return true
        }

        const backtracking = (path, startIndex) => {
            // 第2點：遞歸結束條件，收集結果
            if (startIndex >= s.length) {
                if (path.length === 4) {
                    result.push(path.join('.'))
                }
                return
            }

            let needSegmentsCount = 4 - path.length
            let remainCharCount = s.length - startIndex
            /*
            條件1：要構成一個有效 IP 的字符串個數 大於 剩餘的字符串個數，則非法，不可能構成有效 IP。有效的 IP 至少1個字符，所以 needSegmentsCount < remainCharCount
            條件2：如果現有3個 IP 段了，且總長度為 currentCount。接下去需要尋找到一個合法的 IP 段，那麼合格的 IP 段最長為3.
            所以：
            所需要的段個數為 needSegmentsCount。其中每個有效的 IP 段，長度為 [1, 3]
            剩餘字符串個數為：remainCharCount
            所以：
            - 剩餘字符串過少不行：needSegmentsCount * 1 > remainCharCount 
            - 剩餘字符串過多也不行：remainCharCount > needSegmentsCount * 3
            */

            // 第3點：
            if (remainCharCount < needSegmentsCount || remainCharCount > needSegmentsCount*3) {
                return
            }

            // 第4點：避免 for 多次重複計算
            let upperBound = Math.min(startIndex + 3, s.length)
            for (let i = startIndex; i < upperBound; i++) {
                let IPSegmentTestString = s.substring(startIndex, i + 1)
                if (Number(IPSegmentTestString) < 0 || Number(IPSegmentTestString) > 255) {
                    break
                }
                if (IPSegmentTestString.length > 1 && IPSegmentTestString[0] === '0') {
                    break
                }
                path.push(IPSegmentTestString)
                backtracking(path, i + 1)
                path.pop()
            }
        }
        backtracking([], 0)
        return result
    };

可以看到正確的剪枝，時間複雜度、空間複雜度大大提高了