Backtracking 回溯法 – 陪你刷題

Leetcode 邁向千題的關卡,想要把所有題目刷過一遍,對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難,因此想要將刷題常用的觀念技巧與其對應題目整理出來,一方面可以整理自己思緒,也可以做為未來複習用。
這系列文章會一直持續下去,算是作為工程師職涯的隨身裝備。

何謂回溯法

回溯法的處理方式就像窮舉法,將所有可能的路徑都窮舉出來,接著開始每條岔路都派人走下去,換個角度來看,其實這個過程就如同在決策樹或是多子樹上遍歷 (Tree Traversal) 。

但如果把每條路都確實走過,這樣的作法的時間複雜度相當高,所以回溯法有時可以使用剪枝 (pruning) 的技巧提高效率,不用將所有解法都窮舉出來。

回溯法大部份用來解決廣義的搜索問題,從許多可能的解中找出滿足要求的所有解,回溯法可以應用於以下類型

回溯法操作框架

在使用回溯技巧前,需要先決定好3個條件:

  1. 路徑:已經做出的選擇
  2. 選擇清單:當下可以做的選擇有哪些,做完的選擇會被放到路徑中
  3. 終止條件:到達決策樹的終點,已經無法再往下走

回溯法適合以遞迴 recursion 來解,其核心概念就是將選擇清單裡的選項都逐一執行(窮舉)。

透過 for loop 選取其中一個選項並進行遞迴往下走,在遞迴之後撤銷選擇,藉住 for loop 進而達成清單裡所有的選項都能夠被選取並遞迴。

vector<vector<int>> result;
void backtrack_helper (路徑, 下一步選擇清單)
{
    if ( 終止條件 )
        result.add (路徑);
        return;
    for 下一步 in 選擇清單
        做選擇
        backtrack_helper (路徑, 下一步選擇清單)
        撤銷選擇
}

接下來透過例題,實際來看如何訂出 3 個條件與套用回溯法框架。

Leetcode #77 Combinations

題目敘述:

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

高中數學的排列組合,要找出所有可能的組合問題。首先考慮清楚回溯法的 3 個條件,可以做的選擇就是 n 個整數,而終止條件則是已經選了 k 個數字。

下圖畫出 input 為 n = 4, k = 2 整個決策樹的過程,其中每個點的列表代表路徑,也就是已經做出的選擇,當路徑內個數達到 k ,代表終止條件滿足了。

leetcode_77_1

接著透過下圖來解釋 "回溯" 的精神,在開頭時,我們的選擇清單有 [ 1, 2, 3, 4 ] ,先選擇 1 ,並且再次使用相同函式遞迴下去,接著在遞迴後面,撤銷剛剛所做的選擇,回到了決策樹的頂端,此時的選擇清單又變回了 [ 1, 2, 3, 4 ] ,接著可以選擇 2,透過這樣的方式將清單內所有選項逐一選擇,完成窮舉所有的可能性 。

leetcode_77_2

接下來我們來看程式碼, backtracking 通常以遞迴實作,底下的 combinationsHelper() 就是遞迴的實作,接著來看 3 個條件,其他路徑就是變數 record ,選擇清單則由變數 start 和 n 之間的範圍所構成,終止條件則看路徑內的數量是否已經有 k 個了。

vector<vector<int>> result;
vector<vector<int>> combine(int n, int k) {
    vector<int> record;
    combinationsHelper(record, 1, n, k);
    return result;
}

void combinationsHelper(vector<int> &record, int start, int n, int k)
{
    if (record.size() == k)
    {
        result.push_back(record);
        return;
    }

    for (int i=start; i<=n; i++)
    {
        record.push_back(i);
        combinationsHelper(record, i+1, n, k);
        record.pop_back();
    }
}

時間複雜度

題目要從 n 個整數,要找出 k 個數字的組合。時間負責度為 O ( (C n 取 k) x k) ,C n 取 k 代表可以找出多少組組合,每找出一組,就需要將 k 個數字收集。 至於過程中 push_back 或 pop_back 都只是常數級別操作,可忽略。

空間複雜度

與時間複雜度相同,需要將每組結果存下來。

Leetcode #40 Combination Sum II

題目敘述:

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

構建多子樹前,3個條件必須先想清楚:

  1. 路徑要填的即為選取的 candidates 。
  2. 題目要求每個數只能被使用一次,因此被選擇過的數字都要從選擇清單中剔除。
  3. 終止條件即路徑內的總和等於 target 。

應用剪枝技巧

先將 candidates list 排序後,sorting 的時間複雜度為 O (n*log n),若是不透過剪枝,將所有路徑窮舉出來的時間複雜度可以到 O(n ^2),因此透過 sorting 來達成剪枝將有利於降低時間複雜度,還有另一個好處,當選擇清單的下一個元素比剩餘目標還要大,那該條路線就可以直接放棄,這就是一種剪枝的技巧。

至此,我們可以透用回溯框架來解決本題:

class Solution {
public:
    vector<vector<int>> result;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> record;
        std::sort (candidates.begin(), candidates.end());
        sumHelper(candidates, target, record, 0);
        return result;
    }
private:
    void sumHelper(vector<int>& candidates, int remain, vector<int> &record, int start_index)
    {
        if (remain == 0)
        {
            result.push_back(record);
            return;
        }
        /**
         *  pruning 1. start_index == candidates.size()
         *          2. remain < 0
         */
        for (int i=start_index; i<candidates.size(); i++)
        {
            remain -= candidates[i];
            if (remain >= 0)
            {
                record.push_back(candidates[i]);
                sumHelper (candidates, remain, record, i+1);
                record.pop_back();
            }
            remain += candidates[i];
        }
    }
};

提交後,可以發現有 case 是無法通過,來探討以下 case

Input: Candidates = [1,2,7,1,5], Target = 8

如果以上面的程式碼,會得到以下結果

Output: [[1,2,5],[1,7],[1,2,5],[1,7]]

題目要求不能有重複組合,但當前的算法無法避免重複的解。我們將多子樹的決策過程畫出來如下圖,藍色字為路徑,綠色字為選擇清單,在第一輪的窮舉過程中,由於清單中有重複的元素 1,使得進入第2輪後會出現重複路徑 [1, 2] [1, 5] [1, 7] ,這也是為什麼最後窮舉出重複的答案。

leetcode_40

為了避免這種狀況,在每一輪的挑選中,應該避免重複挑選到相同的元素,因此我們在每一輪的遍歷中,應該跳過重複的元素,最後程式碼如下:

class Solution {
public:
    vector<vector<int>> result;
    vector<vector<int>> combinationSum2 (vector<int>& candidates, int target) {
        vector<int> record;
        std::sort (candidates.begin(), candidates.end());
        sumHelper (candidates, target, record, 0);
        return result;
    }
private:
    void sumHelper (vector<int>& candidates, int remain, 
                    vector<int> &record, int start_index)
    {
        if (remain == 0)
        {
            result.push_back(record);
            return;
        }
        /**
         *  pruning 1. start_index == candidates.size()
         *          2. remain < 0
         */
        for (int i=start_index; i<candidates.size(); i++)
        {
            remain -= candidates[i];
            if (remain >= 0)
            {
                record.push_back(candidates[i]);
                sumHelper (candidates, remain, record, i+1);
                record.pop_back();
            }
            remain += candidates[i];
            /**
             * In same round, duplidcate elements 
             * cann't be choosed again.
             */
            while ((i+1) != candidates.size()
                    && candidates[i+1] == candidates[i])
                i++;
        }
    }
};

時間複雜度

最壞情況下要將 n 個數字都走訪過,需耗費 O (2 ^ n) ,而 sorting 需耗費 O (n logn),總體時間複雜度為 O (2^n)

空間複雜度

使用了一個 vector 來記錄選取過的元素,需耗費 O (n),在回朔法過程不斷發生遞迴, function call stack 也會耗費 O (n) ,整體空間複雜度為 O (n) 。

Leetcode #46 Permutations

題目敘述:

Given a collection of distinct integers, return all possible permutations.

此題要找出所有的排列,終止條件即為路徑內數量等於 nums.size() ,另外一個特別的點在於每個數都會被選擇,因此在"做選擇"這個動作上,採取 swap 來做選擇,選過的放到前面,沒被選的就被 swap 到後面,其餘套用框架後就可以輕鬆解決。

public:
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector <int>> result;
    permuteHelper (result, 0, nums);
    return result;
}

private:
void permuteHelper (vector<vector<int>> &result,
                    int start, vector<int>& nums)
{
    if (start == nums.size())
    {
        result.push_back(nums);
        return;
    }

    for (int i=start; i<nums.size(); i++)
    {
        // 做選擇
        swap (nums[start], nums[i]);
        permuteHelper (result, start+1, nums);
        // 撤銷選擇
        swap (nums[i], nums[start]);
    }
}

時間複雜度

O (N!)。 對於每一個 first element (會有 N 個 first element),之後會執行 (N-1)! 個選擇 ,總共需要 O (N!) 。

空間複雜度

O (N!) 。考慮到有 N! 種可能答案,空間複雜度總共要 O(N x N!) 。

Leetcode #47 Permutations II

題目敘述:

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

這題與 #46 的查別在於 input 內包含重複的元素,如果透過跟上題一樣的解法,會找出重複的解。

下面將整個決策樹畫出來,可以發現,只要每一輪的選擇清單內有重複元素,最後就會得到重複的答案。

leetcode_47

解法就是在每輪的從選擇清單做選擇時,透過一個 hash table 的協助,避免重複選擇相同元素。

class Solution {
public:
    vector<vector<int>> result;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        permuteHelper (nums, 0);
        return result;

    }
    void permuteHelper(vector<int> &nums, int start_index)
    {
        if (start_index == nums.size())
        {
            result.push_back(nums);
            return;
        }

        unordered_set<int> st;
        for (int i=start_index; i<nums.size(); i++)
        {
            if (st.count(nums[i]) == 1)
                continue;
            st.insert(nums[i]);
            swap (nums[start_index], nums[i]);
            permuteHelper(nums, start_index+1);
            swap (nums[i], nums[start_index]);
        }
    }
};

時間複雜度

如同前一題,但差別在於重複的元素可以跳過,可以歸納出時間複雜度會略優於 O (N!)。

空間複雜度

比起 #46 多用了一個 hash table ,整體空間複雜度總共要 O(N x N!) 。

總結

整個回溯法過程,就如同遍歷一個多子樹,要如何造出一個多子樹,必須先想清楚 3 個條件:

  1. 已經做的選擇
  2. 選擇清單
  3. 終止條件

有了以上 3 個條件,即可造出一個多子樹來幫助窮舉所有的答案。

窮舉過程中不斷執行以下步驟:

  1. 先做出選擇並將選擇的節點紀錄在"路徑"中
  2. 接著可以從"選擇清單"中挑出下一個路徑,挑出下一步通常由遞迴來實現
  3. 在遞迴之後必須撤銷選擇

這樣的選擇與撤銷選擇的作法完美的實現回溯,當"終止條件"滿足時,就將路徑紀錄到結果集合之中。

基本上可以透過動態規劃或是貪婪演算法解決的題目,都可以透過 backtracking 來解決,backtracking 窮舉所有答案的,因此其時間複雜度來到指數級別,在資料量不大時使用 backtracking 會是比較好的方式。

參考資料

  1. 演算法筆記 - Backtracking
  2. 回溯算法(DFS 算法)- labuladong
  3. A general approach to backtracking questions in Java - Leetcode discussion

Updated on 2021-06-29 07:53:58 星期二