Backtracking

回溯法（Backtracking）是一種窮舉搜尋（Exhaustive Search）的策略，通常配合「剪枝」技術來提早放棄錯誤的路。

像是在走迷宮。當走到一個分叉路口，先選一條路往前走；如果走到死路，則退回上一個路口，改走另一條路，直到把所有可能的出路都試完為止。

範例

直接以 Leetcode 題目作為範例說明。

題目：列舉 nums 數字的所有排列組合，nums 中沒有重複的數字

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

var permute = function(nums) {
    const n = nums.length
    const result = []
    const curr = []
    const seen = new Set()

    function helper() {
        if (curr.length === n) {
            result.push([...curr])
            return
        }
        for (let i = 0; i < n; i++) {
            if (seen.has(nums[i])) continue // 已經放進備選名單，所以跳過
            curr.push(nums[i])
            seen.add(nums[i])
            helper()
            curr.pop()
            seen.delete(nums[i])
        }
    }

    helper()
    return result
};

Time Complexity: O(n!)
- 回想中學數學的排列組合，第一個位置有 n 種選擇，第二個位置有 n-1 種選擇...，因此相乘之後是 n!
Space Complexity: O(n!)，若不包含輸出內容則為 O(n)

範例​

範例