一文學會回溯算法解題技巧

原文連結

一、前言

我們學習了深度優先搜尋和廣度優先搜尋，相信大家對這兩者的算法有了比較清楚的認識，值得一提的，深度優先算法用到了回溯的算法思想，這個算法雖然相對比較簡單，但很重要，在生産上廣泛用在正規表達式，編譯原理的文法分析等地方，很多經典的面試題也可以用回溯算法來解決，如八皇後問題，排列組合問題，0-1背包問題，數獨問題等，也是一種非常重要的算法。

本文将會從以下幾個方面來講述回溯算法，相信大家看了肯定有收獲！

什麼是回溯算法
回溯算法解題通用套路
經典習題講解

二、什麼是回溯算法

回溯算法本質其實就是枚舉，在給定的枚舉集合中，不斷從其中嘗試搜尋找到問題的解，如果在搜尋過程中發現不滿足求解條件，則「回溯」傳回，嘗試其它路徑繼續搜尋解決，這種走不通就回退再嘗試其它路徑的方法就是回溯法，許多複雜的，規模較大的問題都可以使用回溯法，是以回溯法有「通用解題方法」的美稱。

三、回溯算法解題通用套路

為了有規律地求解問題，我們把問題分成多個階段，每個階段都有多個解，随機選擇一個解，進入下一個階段，下一個階段也随機選擇一個解，再進入下一個階段...

每個階段選中的解都放入一個「已選解集合」中，并且要判斷「已選解集合」是否滿足問題的條件（base case）,有兩種情況

如果「已選解集合」滿足問題的條件，則将「已選解集合」放入「結果集」中，并且「回溯」換個解再周遊。
如果不滿足，則「回溯」換個解再周遊

根據以上描述不難得出回溯算法的通用解決套路僞代碼如下:

function backtrace(已選解集合,每個階段可選解) {
    if (已選解集合滿足條件) {
        結果集.add(已選解集合);
        return;
    }
    // 周遊每個階段的可選解集合
    for (可選解 in 每個階段的可選解) {
        // 選擇此階段其中一個解,将其加入到已選解集合中
        已選解集合.add(可選解)
        // 進入下一個階段
        backtrace(已選解集合,下個階段可選的空間解)
        // 「回溯」換個解再周遊
        已選解集合.remove(可選解)
    }
}

通過以上分析我們不難發現回溯算法本質上就是深度優先周遊，它一般解決的是樹形問題（問題分解成多個階段，每個階段有多個解，這樣就構成了一顆樹），是以判斷問題是否可以用回溯算法的關鍵在于它是否可以轉成一個樹形問題。

另外我們也發現如果能縮小每個階段的可選解，就能讓問題的搜尋規模都縮小，這種就叫「剪枝」，通過剪枝能有效地降低整個問題的搜尋複雜度！之前我們在一文學會遞歸解題中求解斐波那契問題時就用到了減枝的技巧，使問題的空間大大減少（如下圖示）

綜上，我們可以得出回溯算法的基本套路如下：

将問題分成多個階段，每個階段都有多個不同的解，這樣就将問題轉化成了樹形問題，這一步是問題的關鍵！如果能将問題轉成樹形問題，其實就成功了一半，需要注意的是樹形問題要明确終止條件，這樣可以在 DFS 的過程中及時終止周遊，達到剪枝的效果
套用上述回溯算法的解題模闆，進行深度優先周遊，直到找到問題的解。

隻要兩個步驟，是不是很簡單！接下來我們套用以上的解題模闆來看看怎麼使用以上回溯算法解題套路來解幾道經典的問題。

四、經典習題講解

全排列

給定數字 1，2，3，求出 3 位不重複數字的全排列

1、将問題轉為樹形結構

由于求的是 3 位數的全排列，是以問題分解為 3 個階段，第一個階段可以選 1，2，3 三個解，如果第一階段選完數字後，第二個階段可以選另外 2 個解，同理第三個階段也可以選擇剩下一個解。樹形結構如下：

2、套用上述回溯算法的解題模闆，進行深度優先周遊，直到找到問題的解

代碼如下:

public class Solution {
    /**
     * 結果集
     */
    private static List<String> RESULT = new ArrayList<>(10);
    /**
     * 參與全排列的數字
     */
    private static List<Integer> NUMS = Arrays.asList(1, 2, 3);
    /**
     * 周遊目前階段的解
     * @param selectedNums   已選解集合
     * @param selectableNums 可選的解集合
     */
    public static void permutation(List<Integer> selectedNums, List<Integer> selectableNums {
        // 滿足條件，加入結果集
        if (selectedNums.size() == NUMS.size()) {
            RESULT.add(Arrays.toString(selectedNums.toArray()));
            return;
        }
        // 周遊每個階段的可選解集合
        for (int i = 0; i < selectableNums.size(); i++) {
            Integer num = selectableNums.get(i);
            // 去除不符合條件的解，減枝
            if (selectedNums.contains(num)) {
                continue;
            }
            // 選擇目前階段其中一個解
            selectedNums.add(num);
            // 選完之後再進入下個階段周遊
            permutation(selectedNums, selectableNums);
            // 回溯,換一個解繼續周遊
            selectedNums.remove(num);
        }
    }
    public static void main(String[] args) {
        List<Integer> selectedNums = new ArrayList<>();
        permutation(selectedNums, NUMS);
        System.out.println(Arrays.toString(RESULT.toArray()));
    }
}

為了讓大家更好地了解上述代碼，我一步步地畫出了每個階段的解題圖解，對照着以上代碼看相信大家應該能看明白

0-1背包問題

這裡介紹一下一種比較簡單的背包問題：

有一個背包，背包總的承載重量是 Wkg。現在我們有 n 個物品，每個物品的重量不等，并且不可分割。我們現在期望選擇幾件物品，裝載到背包中。在不超過背包所能裝載重量的前提下，如何讓背包中物品的總重量最大？假設這 n 個物品的品質分别 3kg, 4kg, 6kg, 8kg，背包總的承載重量是 10kg。

套用回溯算法解題思路

由于有 n 個物品，是以問題可以分解成 n 個階段，第一個階段可以有 n 個物品可選，第二個階段有 n-1 個物品可選,,,,,,最後一個階段有 1 個物品可選，不難畫出以下遞歸樹

既然能轉成樹形結構，那我們進入步驟 2

需要注意的，進行 DFS 的終止條件是什麼呢，顯然是所選物品品質（周遊的節點）和大于等于背包品質，稍加變形不難得出以下代碼

public class Solution {
    /**
     * 結果集
     */
    private static Integer RESULT = 0;
    /**
     * 背包最大承載品質
     */
    private static Integer KNAPSACK_MAX_WEIGHT = 10;
    /**
     * 現有背包
     */
    private static List<Integer> WEIGHTS = Arrays.asList(3, 4, 6, 8);
    /**
     * 周遊目前階段的解
     *
     * @param selectedWeights  已選解集合
     * @param selectableWeight 可選的解集合
     */
    public static void knapsack(List<Integer> selectedWeights, List<Integer> selectableWeight) {
        {
            // 求已選物品的總重量
            int sumOfWeights = selectedWeights.stream().mapToInt(Integer::intValue).sum();
            if (sumOfWeights == KNAPSACK_MAX_WEIGHT) {
                RESULT = Math.max(RESULT, sumOfWeights);
                return;
            } else if (sumOfWeights > KNAPSACK_MAX_WEIGHT) {
                // 如果已選物品的總重量超過背包最大承受品質，則要把最後一個選擇的物品移除，再求品質和
                selectedWeights.remove(selectedWeights.size() - 1);
                sumOfWeights = selectedWeights.stream().mapToInt(Integer::intValue).sum();
                RESULT = Math.max(RESULT, sumOfWeights);
                return;
            } else {
                RESULT = Math.max(RESULT, sumOfWeights);
            }
        }
        // 周遊每個階段的可選解集合
        for (int i = 0; i < selectableWeight.size(); i++) {
            Integer num = selectableWeight.get(i);
            // 去除不符合條件的解，減枝
            if (selectedWeights.contains(num)) {
                continue;
            }
            // 選擇子節點的其中一個解
            selectedWeights.add(num);
            // 選完之後再進行 dfs
            knapsack(selectedWeights, selectableWeight);
            // 「回溯」換個解再周遊
            selectedWeights.remove(num);
        }
    }
    public static void main(String[] args) {
        List<Integer> selectedNums = new ArrayList<>();
        knapsack(selectedNums, WEIGHTS);
        System.out.println("result = " + RESULT);
    }
}

可以看到套用模闆我們又輕松解決了0-1背包問題，可能有人會說以上問題比較簡單，接下來我們來看看如何用上模闆來解八皇後問題。

八皇後

老讀者對八皇後問題應該并不陌生，之前我們在位運算的文章中詳細地講解了如何用位運算來求解八皇後問題，當時也說了，用位運算來求解，是效率最高的，其實八皇後問題也可以用我們的回溯算法來求解，隻不過不是那麼高效而已，不過可讀性更好。

來簡單回顧上什麼是八皇後問題。

八皇後問題：8x8 的棋盤，希望往裡放 8 個棋子（皇後），每個棋子所在的行、列、對角線都不能有另一個棋子

如下所示是 8 皇後問題的一種放法。

對于 N 皇後問題，問題可以分解為 N 個階段，第一個階段即第一行有 N 個解（N 列中的做生意一個解），第二階段（第二行）由于受第一行限制（皇後所在列，斜線不能放），解肯定是少于 N 個解，它的解視第一行所放皇後位置而定,... ，第 N 個階段的解受前面 N-1 個階段解的影響。N 皇後樹形結構如下

套用以上模闆時，注意終止條件與每個階段（每一行）所選解是否合法（剪枝）即可。注意看下 queenSettle 的方法，這是套用我們的回溯算法解題模闆所得出來的，其他方法都是在此模闆上進行添磚加瓦而已。

public class Solution {
    private static Integer N = 8;
    /**
     *
     * @param selectedColumns 已選解集合,下标表示行,值表示queen存儲在哪一列
     * @param row             可選的空間解,第 n 行可選
     */
    public static void queenSettle(int[] selectedColumns, int row) {
        // 終止條件
        if (row > N - 1) {
            // 說明前 N 行都已經都選完皇後了，
            printQueens(selectedColumns);
            return;
        }
        
        for (int i = 0; i < N; i ++) {
            // 剔除不合法的格子
            if (!isValid(row, i, selectedColumns)) {
                continue;
            }
            // 選擇子節點（目前行）其中一個解
            selectedColumns[row] = i;
            // 選完之後再進入下個階段的（下一行）周遊
            queenSettle(selectedColumns, row + 1);
            // 回溯,換一個解繼續 dfs，回溯時要把回溯節點的解移除
            selectedColumns[row] = -1;
        }
    }
    /**
     * 判斷相應的格子放置皇後是否OK
     * @param row
     * @param column
     * @param selectedColumns
     * @return
     */
    private static boolean isValid(int row, int column, int[] selectedColumns) {
        //判斷row行column列放置是否合适
        int leftup = column - 1, rightup = column + 1;
        for (int i = row-1; i >= 0; --i) { // 逐行往上考察每一行
            if (selectedColumns[i] == column) return false; // 第i行的column列有棋子嗎？
            if (leftup >= 0) { // 考察左上對角線：第i行leftup列有棋子嗎？
                if (selectedColumns[i] == leftup) return false;
            }
            if (rightup < 8) { // 考察右上對角線：第i行rightup列有棋子嗎？
                if (selectedColumns[i] == rightup) return false;
            }
            --leftup; ++rightup;
        }
        return true;
    }
    public static void main(String[] args) {
        int[] selectedColumn = new int[N];
        // 從第 0 行開始 DFS
        queenSettle(selectedColumn, 0);
    }
    private static void printQueens(int[] result) { // 列印出一個二維矩陣
        for (int row = 0; row < 8; ++row) {
            for (int column = 0; column < 8; ++column) {
                if (result[row] == column) System.out.print("Q ");
                else System.out.print("* ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

可以看到八皇後這麼複雜的問題套用以上的解題模闆也被我們輕松解決了！

五、總結

使用回溯算法解題的關鍵是把問題分成多階段，每個階段都有相應的解，于是就把問題轉成了樹形問題，轉成樹形問題後，剩下的隻需要套用上文總結的解題模闆即可，尤其需要注意的是，當周遊目前階段解的時候，可以根據之前階段的解作「剪枝」操作，這樣使問題的搜尋規模變小，有效降低了問題的複雜度。

來源 | 碼海

作者 | 碼海

一文學會回溯算法解題技巧

一、前言

二、什麼是回溯算法

三、回溯算法解題通用套路

四、經典習題講解

全排列

0-1背包問題

八皇後

五、總結

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希