Backtracking algorithm 回溯算法

什么是回溯算法

回溯算法是一种通用的算法。回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

• 找到一个可能存在的正确的答案
• 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。回溯算法的本质就是暴力的递归搜索，当然在实际的操作中。可以通过适当的剪枝以减少时间复杂度。

leetcode回溯算法相关题目解答

以下题目均来自leetcode

? 子集

思路

本题需要注意的是，因为不能包含重复的子集([1,2,3],[3,1,2]是属于重复的)，所以"3"这个节点下，不需要添加"1"和"2"节点进行递归操作，回产生重复的集合。

解答

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const result = []

    result.push([])

    const fn = (head, tail) => {
        for (let i = 0; i < tail.length; i++) {
            result.push([...head, tail[i]])
            if (tail.slice(i + 1)) {
                fn([...head, tail[i]], tail.slice(i + 1))
            }
        }
    }

    for (let i = 0; i < nums.length; i++) {
        result.push([nums[i]])
        if (nums.slice(i + 1).length) {
            fn([nums[i]], nums.slice(i + 1))
        }
    }


    return result;
};

? 子集 II

思路

首先将数组进行排序。排序的目的是将相等的元素，移动到相邻的位置。我们在遍历数组的时候，判读当前的值和前一个的值是否相等，如果相等则跳过

解答

? 同层减枝去重

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    const result = []

    result.push([])

    nums.sort((a, b) => a - b)

    const fn = (head, tail) => {
        for (let i = 0; i < tail.length; i++) {
            if (tail[i] === tail[i - 1]) {
                continue
            } else {
                result.push([...head, tail[i]])
                if (tail.slice(i + 1)) {
                    fn([...head, tail[i]], tail.slice(i + 1))
                }
            }
        }
    }

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) {
            continue
        } else {
            result.push([nums[i]])
            if (nums.slice(i + 1).length) {
                fn([nums[i]], nums.slice(i + 1))
            }
        }  
    }

    return result;
};

? 另外的思路，使用hash去重

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    const result = []
    const hash = {}

    result.push([])

    nums.sort((a, b) => a - b)

    const fn = (head, tail) => {
        for (let i = 0; i < tail.length; i++) {
            let key = [...head, tail[i]].join(',')
            if (!hash[key]) {
                result.push([...head, tail[i]])
                hash[key] = true;
            }
            if (tail.slice(i + 1)) {
                fn([...head, tail[i]], tail.slice(i + 1))
            }
        }
    }

    for (let i = 0; i < nums.length; i++) {
        let key = [nums[i]].join(',')
        if (!hash[key]) {
            result.push([nums[i]])
            hash[key] = true;
        }
        if (nums.slice(i + 1).length) {
            fn([nums[i]], nums.slice(i + 1))
        }
    }


    return result;
};

? 组合

思路

n，是我们的取值范围。k是我们的递归次数。当递归的次数等于2时，结束递归。将满足条件的添加到result中，并返回。

解答

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    const arr = []
    const result = []

    // 初始化
    for (let i = 1; i <= n; i++) {
        arr.push(i)
    }

    if (arr.length === k) {
        // 如果k等于长度，直接返回集合
        return [arr];
    }

    const fn = (head, tail, k) => {
        if (k <= 0) {
           result.push(head) 
        } else {
            for (let i = 0; i < tail.length; i++) {
                fn([...head, tail[i]], tail.slice(i + 1), k - 1)
            }
        }
    }

    for (let i = 0; i < arr.length; i++) {
        if (k > 0) {
            fn([arr[i]], arr.slice(i + 1), k - 1);
        }
    }

    return result;
};

? 组合总和

思路

虽然集合中的数字是可以重复利用的。为了进行优化，我们还是需要做适当的减枝，避免做过多的递归。比如"2"节点的子节点是"2,3,6,7"。"3"节点的子节点是"3,6,7", 为什么没有"2"呢？因为如果有"2",会和之前的"2->3"重复，所以可以少递归这一条分支。

解答

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    const result = []
    candidates.sort((a, b) => a - b)

    const fn = (arr, sum, index) => {
        if (sum > target) {
            return
        }
        if (sum === target) {
            result.push(arr)
        } else {
            // i = index, 避免重复的递归，同时避免重复
            for (let i = index; i < candidates.length; i++) {
                fn([...arr, candidates[i]], sum + candidates[i], i)
            }
        }
    }

    for (let i = 0; i < candidates.length; i++) {
        if (candidates[i] === target) {
            result.push([candidates[i]])
        } else {
            fn([candidates[i]], candidates[i], i)
        }
    }

    return result;
};

? 组合总和 II

思路

思路和组合总和一致。只是多了一些判读条件。首先将数组排序，把大小相等的元素集中在一起。在递归的视频，判读当前和前一个元素是否相等，如果相等则跳过。避免重复的组合。

注意这里是不能重复使用同一个数字，不是不能包含重复的数字。，所以出现重复的数字是允许的，添加上述判读条件的目的是为了出现重复的组合。见下图：

解答

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    const result = []
    candidates = candidates.sort((a, b) => a - b)

    const fn = (sum, arr, candidates) => {
        if (sum > target) {
            return
        }
        if (sum === target) {
            result.push(arr)
        } else {
            for (let i = 0; i < candidates.length; i++) {
                if (candidates[i] !== candidates[i - 1]) {
                    let temp = candidates.slice(i + 1)
                    fn(sum + candidates[i], [...arr, candidates[i]], temp)
                }
            }
        }
    }

    for (let i = 0; i < candidates.length; i++) {
        if (candidates[i] === target && candidates[i] !== candidates[i - 1]) {
            result.push([candidates[i]])
        } else if (candidates[i] !== candidates[i - 1]) {
            let temp = candidates.slice(i + 1)
            fn(candidates[i],[candidates[i]],temp)
        }
    }

    return result;
};

? 组合总和 III

思路

和“组合”题目类似，k就是我们的递归次数。n是我们的target，当递归层数达到k时，结束递归。同时将满足条件的组合，添加到结果中

解答

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const result = [];
    const candidates = [];
    const target = n;

    // 初始化
    for (let i = 1; i <= 9; i++) {
        candidates.push(i)
    }

    const fn = (sum, arr, candidates, k) => {
        if (k >= 0) {
            if (k === 0) {
                if (sum === target) {
                    result.push(arr)
                }
            } else {
                for (let i = 0; i < candidates.length; i++) {
                    const temp = candidates.slice(i + 1)
                    fn(
                        sum + candidates[i],
                        [...arr, candidates[i]],
                        [...temp],
                        k - 1
                    );
                }
            }
        }
    }

    for (let i = 0; i < candidates.length; i++) {
        if (k === 1 && candidates[i] === target) {
            result.push([candidates[i]])
        } else {
            const temp = candidates.slice(i + 1)
            fn(
                candidates[i],
                [candidates[i]],
                [...temp],
                k - 1
            )
        }
    }

    return result;
};

? 电话号码的字母组合

思路

// 电话号码数字对应的字母
{
    2: ['a', 'b', 'c'],
    3: ['d', 'e', 'f'],
    4: ['g', 'h', 'i'],
    5: ['j', 'k', 'l'],
    6: ['m', 'n', 'o'],
    7: ['p', 'q', 'r', 's'],
    8: ['t', 'u', 'v'],
    9: ['w', 'x', 'y', 'z']
}

解答

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {

    const map = {
        2: ['a', 'b', 'c'],
        3: ['d', 'e', 'f'],
        4: ['g', 'h', 'i'],
        5: ['j', 'k', 'l'],
        6: ['m', 'n', 'o'],
        7: ['p', 'q', 'r', 's'],
        8: ['t', 'u', 'v'],
        9: ['w', 'x', 'y', 'z']
    }
    const arr = digits.split('')
    const result = []

    const fn = (head, arr) => {
        if (arr.length) {
            const key = arr.splice(0, 1)[0]
            const collection = map[key]
            for (let i = 0; i < collection.length; i++) {
                fn(`${head}${collection[i]}`, [...arr])
            }
        } else {
            if (head) {
                result.push(head)
            }
        }
    }

    fn('', [...arr]);

    return result;
};

全排列

思路

注意已经添加到结果中的数字，不参与下次递归。

解答

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const result = []

    const fn = (head, tail) => {
        for (let i = 0; i < tail.length; i++) {
            let temp = [...tail]
            temp.splice(i, 1)
            if (temp.length) {
                fn([...head, tail[i]], temp);
            } else {
                result.push([...head, tail[i]])
            }
        }
    }

    for (let i = 0; i < nums.length; i++) {
        let temp = [...nums]
        temp.splice(i, 1)
        if (temp.length) {
            fn([nums[i]], temp);
        } else {
            result.push([nums[i]])
        }
    }

    return result;
};

全排列 II

思路

思路和之前的题目都是类似的，首先对数组进行排序，目的是将相等的数字集中到一起。如果在同一层的递归中出现同样的数字，跳过。避免出现重复的排列。

解答

? 使用hash去重

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    const result = []
    const hash = {}

    nums.sort((a, b) => a - b)

    const fn = (head, tail) => {
        for (let i = 0; i < tail.length; i++) {
            let temp = [...tail]
            temp.splice(i, 1)
            if (temp.length) {
                fn([...head, tail[i]], temp);
            } else {
                let key = [...head, tail[i]].join(',');
                if (!hash[key]) {
                    result.push([...head, tail[i]])
                    hash[key] = true
                }   
            }
        }
    }

    for (let i = 0; i < nums.length; i++) {
        let temp = [...nums]
        temp.splice(i, 1)
        if (temp.length) {
            fn([nums[i]], temp);
        } else {
            result.push([nums[i]])
        }
    }

    return result;
};

? 同层剪枝

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    const result = []

    nums.sort((a, b) => a - b)

    const fn = (head, tail) => {
        for (let i = 0; i < tail.length; i++) {
            let temp = [...tail]
            temp.splice(i, 1)
            if (tail[i] !== tail[i - 1]) {
                if (temp.length) {
                    fn([...head, tail[i]], temp);
                } else {
                    result.push([...head, tail[i]])
                }
            }
        }
    }

    for (let i = 0; i < nums.length; i++) {
        let temp = [...nums]
        temp.splice(i, 1)
        if (nums[i] !== nums[i - 1]) {
            if (temp.length) {
                fn([nums[i]], temp);
            } else {
                result.push([nums[i]])
            }
        }
        
    }

    return result;
};

? 复原IP地址

思路

终于看到一个不那么雷同的题目了。之前的全排列，组合，组合总合。解答过程都是大同小异的。

首先确定下本题下,IP地址是否合法的判断条件，首先需要有4组数字组合，每一组数字大小范围在0～255（包含255），其中不能包含前置的0。也就是说"02","022"是不合规的。

题目提供了一段数字，根据上述的规则，我们需要在这段数字中添加3个点对这个数字进行分割（也就是说需要递归3层）。我们把递归的过程用图表示出来（由于分叉太多，所以图片并不完整，还请见谅）

橘红色的代表，IP地址不合规的，无法继续迭代下去。

解答

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
    const result = [];

    const isLegal = (n) => {
        if (n.length <= 0) {
            return false
        }
        if (n.length > 1 && n[0] === '0') {
            return false
        }
        if (Number(n) > 255 || Number(n) < 0) {
            return false
        }
        return true
    }

    const fn = (head, tail, n) => {        
        if (n <= 0) {
            if (isLegal(tail)) {
                result.push(`${head}.${tail}`)
            }
        } else {
            for (let i = 0; i < 3; i++) {
                const h = tail.slice(0, i + 1);
                if (isLegal(h)) {
                    let newHead = ''
                    if (head.length) {
                        newHead = `${head}.${h}`;
                    } else {
                        newHead = `${h}`;
                    }
                    const t = tail.slice(i + 1);
                    fn(newHead, t, n - 1);
                }
            }
        }
    };

    fn('', s, 3);

    return result;
};

括号生成

思路

在进行回溯之前，首先需要确定下，递归的终止条件。

在一段括号组成的字符串中，添加'('是无需判断条件的，但是添加')'是需要额外的判断条件。只有在这段字符串'('的数量大于')'的情况下，才允许添加')'

比如: '(())'，在这个时候添加')'字符串，括号将永远无法闭合。再比如，'()((', 就可以添加')'字符串。

我们使用下图，来描述回溯的过程

解答

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const result = []
    const left = []
    const rigth = []

    const fn = (head, leftNum, rightNum) => {
        if (leftNum === n && rightNum === n) {
            result.push(head)
        } else {
            if (leftNum >= rightNum) {
                if (leftNum < n) {
                    fn(`${head}(`, leftNum + 1, rightNum)
                }
                if (rightNum < n && rightNum + 1 <= leftNum) {
                    fn(`${head})`, leftNum, rightNum + 1)
                }
            }
        }
    }

    fn('', 0, 0);

    return result;
};

? N皇后

思路

终于讲到了N皇后问题。先说下解决这题的思路，依然是使用递归的方法。我们首先假定第一个Queen在[0, 0]的位置，然后确定第一个Queen的攻击范围（既之后的Queen不能放的位置）。接着开始遍历棋盘的第二行，找到可以放的位置，并记录第二个Queen的攻击位置，之后的Queen要同时避免第一个Queen和第二个Queen的攻击位置。然后开始查找第三行。

如果找不到，我们需要向上回溯到第一行。并同时把第二行Queen的攻击位置，恢复到可以放置的状态。然后将第一个Queen移动到[0, 2]的位置。然后接着遍历棋盘的第二行。

关于Queen的攻击范围，在国际象棋中Queen可以攻击直线，横线，左斜线，右斜线的敌人。比如下图，红色的部分就是Queen的攻击范围。攻击范围内，是不能放置第二个Queen的。

直线的攻击范围容易确定，斜线的攻击范围呢？使用 4 * 4 的棋盘说明，左斜线可以分为 3 2 1 0 -1 -2 -3 , 7条斜线。

右斜线可以分为 1，2，3，4，5，6 , 7条斜线。

我们使用hash记录攻击范围

const letDiagonalAttackRange = {
    3: true,
    2: true,
    1: true,
    0: true,
    -1: true,
    -2: true,
    -3: true
}
const rightDiagonalAttackRange = {
    0: true,
    1: true,
    2: true,
    3: true,
    4: true,
    5: true,
    6: true,
}

比如当Queen在[1， 1]的位置时，我们将letDiagonalAttackRange[0]和rightDiagonalAttackRange[2]设置为false，之后的Queen运动到坐标x+y等于2，或者x-y等于0，的位置时。就能放置，只能继续向后查找。

解答

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    const result = []
    const rowAttackRange = {}
    const colAttackRange = {}
    const letDiagonalAttackRange = {}
    const rightDiagonalAttackRange = {}

    const initializeAttackRange = () => {
        // 初始化直线攻击范围
        for (let i = 0; i < n; i++) {
            rowAttackRange[i] = true
            colAttackRange[i] = true
        }
        // 初始化斜线攻击范围
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                letDiagonalAttackRange[i + j] = true
                rightDiagonalAttackRange[i - j] = true
            }
        }
    }

    initializeAttackRange()

    // 判读是否允许放置
    const isPlace = (x, y) => {
        if (rowAttackRange[y] && colAttackRange[x] && letDiagonalAttackRange[y + x] && rightDiagonalAttackRange[y - x]) {
            return true
        }
        return false
    }

    const fn = (row, collection) => {
        if (row === n) {
            result.push([...collection])
            return
        } else {
            for (let j = 0; j < n; j++) {
                if (isPlace(j, row)) {
                    rowAttackRange[row] = false
                    colAttackRange[j] = false
                    letDiagonalAttackRange[row + j] = false
                    rightDiagonalAttackRange[row - j] = false
                    collection.push({
                        x: j,
                        y: row,
                    })
                    fn(row + 1, collection)
                    // 如果从这个格子往下没有获得解，需要还原
                    rowAttackRange[row] = true
                    colAttackRange[j] = true
                    letDiagonalAttackRange[row + j] = true
                    rightDiagonalAttackRange[row - j] = true
                    collection.pop()
                }
            }
        }
    }

    for (let j = 0; j < n; j++) {
        let temp = [
            {
                x: j,
                y: 0
            }
        ];
        rowAttackRange[0] = false
        colAttackRange[j] = false
        letDiagonalAttackRange[0 + j] = false
        rightDiagonalAttackRange[0 - j] = false
        fn(
            1,
            temp
        )
        rowAttackRange[0] = true
        colAttackRange[j] = true
        letDiagonalAttackRange[0 + j] = true
        rightDiagonalAttackRange[0 - j] = true
    }

    
    // 对result做处理
    for (let i = 0; i < result.length; i++) {
        let temp = new Array(n).fill(new Array(n).fill('.'))
        for (let j = 0; j < n; j++) {
            const { x, y } = result[i][j]
            const arr = [...temp[y]]
            arr[x] = 'Q'
            temp[y] = arr.join('')
        } 
        result[i] = temp     
    }

    return result

};

参考

• 回溯法Wiki
• leetcode