核心概念

  • 窮舉所有可能
  • 透過「撤銷選擇」的方式回到上次做出選擇的分歧點 root，以繼續遍歷其他選擇

套路一：排列

void dfs(選擇, 選擇列表)
{
    if (滿足終止條件) { // 要處裡越界情況
        res.add(路徑);
        return;
    }

    for (const auto& 選擇 : 選擇列表) {
        做選擇;
        dfs(選擇, 選擇列表);
        撤銷選擇;
    }
}

經典例題

套路二：組合／子集

寫法一：

void dfs(選擇, 選擇列表)
{
    if (滿足終止條件) { // 要處裡越界情況
        res.add(path);
        return;
    }

    // 取
    path.addLast(選擇); // 做選擇
    dfs(...);
    path.removeLast(選擇); // 撤銷選擇

    // 不取
    dfs(...);
}

寫法二：

void dfs(選擇, 選擇列表)
{
    if (滿足終止條件) { // 要處裡越界情況
        res.add(路徑);
        return;
    }

    // 若要取, 則會遞迴執行；若不取, 則 for loop 迭代到下一輪
    for (const auto& 選擇 : 選擇列表) {
        // 剪枝
        if (不滿足要取的條件) {
            continue;
        }

        做選擇;
        dfs(選擇, 選擇列表);
        撤銷選擇;
    }
}

經典例題