一看就懂，一写就懵？搞懂回溯算法，一口气刷了20多道题（中）

var totalNQueens = function (n) {
    let count = 0; //皇后可放置的总数
    let isValid = (row, col, board, n) => {
        //所在行不用判断，每次都会下移一行
        //判断同一列的数据是否包含
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') {
                return false
            }
        }
        //判断45度对角线是否包含
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') {
                return false
            }
        }
        //判断135度对角线是否包含
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; j--, i--) {
            if (board[i][j] === 'Q') {
                return false
            }
        }
        return true
    }
    let backTracing = (row, board) => {
        //走到最后一行，统计次数
        if (row === n) {
            count++;
            return
        }
        for (let x = 0; x < n; x++) {
            //判断该位置是否可以放置 皇后
            if (isValid(row, x, board, n)) {
                board[row][x] = 'Q'; //放置皇后
                backTracing(row + 1, board); //递归
                board[row][x] = '.'; //回溯，撤销处理结果
            }
        }
    }
    backTracing(0, board)
    let board = [...Array(n)].map(v => v = ([...Array(n)]).fill('.')) //棋盘
    return count
};

const subsets = (nums) => {
    const res = [];
    const backTracing = (index, list) => {
        res.push(list.slice());     // 调用子递归前，加入解集
        for (let i = index; i < nums.length; i++) { // 枚举出所有可选的数
            list.push(nums[i]);       // 选这个数
            backTracing(i + 1, list);         // 基于选这个数，继续递归
            list.pop();               // 撤销选这个数
        }
    };
    backTracing(0, []);
    return res;
};

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
    let result = [];
    let backTracing = (start, path) => {
        // 如果已经选满了的话，加入结果集中
        if (path.length == k) {
            result.push(path.slice());
            return;
        }
        // 从开始的数字到末尾的数字
        for (let i = start; i <= n; i++) {
            // 加入选择列表中
            path.push(i);
            // 继续深度搜索
            backTracing(i + 1, path);
            // 撤销选择
            path.pop(i);
        }
    };
    backTracing(1, []);
    return result;
};

var combinationSum = function (candidates, target) {
    const result = [], visited = [];
    backTracing(0, 0);
    return result;
    function backTracing(sum, cur) {
        if (target === sum) result.push(visited.slice());
        if (target <= sum) return;
        for (let i = cur; i < candidates.length; i++) {
            visited.push(candidates[i]); //加入到选项里面
            backTracing(sum + candidates[i], i);//选择这个选项，继续递归
            visited.pop(); //插销这个选择
        }
    }
};

var combinationSum3 = function (k, n) {
    let ans = [];
    let backTracing = (start, path) => {
        if (path.length === k && path.reduce((acc, prev) => acc += prev) === n) {
            ans.push(path.slice())
            return
        }
        for (let i = start; i <= 9; i++) {
            path.push(i)
            backTracing(i + 1, path)
            path.pop(i)
        }
    }
    backTracing(1, [])
    return ans
};

var letterCombinations = function (digits) {
    if(!digits.length) return []
    const dic = {
        2: 'abc',
        3: 'def',
        4: 'ghi',
        5: 'jkl',
        6: 'mno',
        7: 'pqrs',
        8: 'tuv',
        9: 'wxyz',
    }, ans = [];
    let backTracing = (cur, index) => {
        if (index > digits.length - 1) { //选项满足长度，加入结果
            ans.push(cur)
            return
        }
        let curDic = dic[digits[index]] //找到当前按钮对应的字母字符串
        for (let prop of curDic) {
            backTracing(cur + prop,index+1) //拼接按钮对应的字符串组合
        }
    }
    backTracing('', 0)
    return ans
};

var waysToStep = function (n) {
    let ans = [], map = [1, 2, 3]
    let backTracing = (path, sum) => {
        if (sum >= n) {
            if (sum == n) {
                ans++;
            }
            return
        }
        for (let i = 0; i < 3; i++) {
            path.push(map[i]);
            backTracing(path, sum + map[i])
            path.pop(i)
        }
    }
    backTracing([], 0)
    return ans
};

/**
 * @param {number} n
 * @return {number}
 */
var waysToStep = function (n) {
    let dp =[],mod = 1000000007;
    dp[0]=0,dp[1]=1,dp[2]=2,dp[3]=4;
    for (let i = 4; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod
    }
    return dp[n]
};