回溯

22. 括号生成

Javascript

function generateParenthesis(n) {
    const res = [];
    backtrack('', 0, 0);
    return res;

    function backtrack(s, left, right) {
        if (s.length === 2 * n) {
            res.push(s);
            return;
        }
        if (left < n) {
            backtrack(s + '(', left + 1, right);
        }
        if (right < left) {
            backtrack(s + ')', left, right + 1);
        }
    }
}

46. 全排列

回溯算法 穷举

做选择的时候需要判断一下 是否已经 选择过了 时间复杂度 O(n!) 空间复杂度 O(n)

Javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
    const ans = [];
    backtrack([], nums);
    return ans;

    function backtrack(path, nums) {
        if (path.length === nums.length) {
            ans.push(path.slice());
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            if (path.includes(nums[i])) {
                continue;
            }
            path.push(nums[i]);
            backtrack(path, nums);
            path.pop();
        }
    }
};

47. 全排列 II

回溯算法

排序后，通过 used 剪枝。

Javascript

function permuteUnique(nums) {
    const res = [];
    const used = Array(nums.length).fill(false);
    nums.sort((a, b) => a - b);

    function backtrack(path) {
        if (path.length === nums.length) {
            res.push([...path]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
                continue;
            }
            path.push(nums[i]);
            used[i] = true;
            backtrack(path);
            path.pop();
            used[i] = false;
        }
    }

    backtrack([]);
    return res;
}

51. N 皇后

Javascript

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
    let map = Array.from({ length: n }, () => new Array(n).fill('.'));
    let ans = [];
    backtrack(0);
    return ans;

    function backtrack(row) {
        if (row === n) {
            ans.push(map.map(arr => arr.join('')));
            return;
        }
        for (let col = 0; col < n; col++) {
            if (!isValid(row, col)) {
                continue;
            }
            map[row][col] = 'Q';
            backtrack(row + 1);
            map[row][col] = '.';
        }
    }

    function isValid(row, col) {
        // 同一列中不能有 Q
        for (let i = 0; i < row; i++) {
            if (map[i][col] === 'Q') return false;
        }
        // 检查左上方是否有冲突 左上角斜线不能有
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (map[i][j] === 'Q') return false;
        }

        // 检查右上方是否有冲突 右上角斜线不能有
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (map[i][j] === 'Q') return false;
        }
        return true;
    }
};

52. N 皇后 II

Javascript

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function (n) {
    let map = new Array(n).fill().map(() => new Array(n).fill('.'));

    return backtrack(0);

    function backtrack(row) {
        if (row === n) {
            return 1;
        }

        let acc = 0;
        for (let col = 0; col < n; col++) {
            if (isValid(row, col)) {
                map[row][col] = 'Q';
                acc += backtrack(row + 1);
                map[row][col] = '.';
            }
        }
        return acc;
    }

    function isValid(row, col) {
        // 检查列中是否已尽有 Q
        for (let i = 0; i < row; i++) {
            if (map[i][col] === 'Q') return false;
        }

        // 检查左上方是否有冲突
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (map[i][j] === 'Q') return false;
        }

        // 检查右上方是否有冲突
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (map[i][j] === 'Q') return false;
        }

        return true;
    }
};