【JavaScript】LeetCode：66-70

66 组合总和

• 回溯
• sum：当前组合的数字和。
• 递归终止条件：sum > target。
• 收集结果条件：sum = target，找到了满足条件的组合。
• 注意：因为可以重复取数，所以下一次遍历的开始索引startIndex为当前遍历的节点索引i。

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    var traversal = function(candidates, target, sum, startIndex){
        if(sum > target){
            return;
        }
        if(sum == target){
            res.push(path.slice());
            return;
        }
        for(let i = startIndex; i < candidates.length; i++){
            sum += candidates[i];
            path.push(candidates[i]);
            traversal(candidates, target, sum, i);
            sum -= candidates[i];
            path.pop();
        }
    };
    let res = [];
    let path = [];
    traversal(candidates, target, 0, 0);
    return res;
};

67 括号生成

• 回溯
• left：左括号的数量，right：右括号的数量。
• left < right：无效。
• 收集结果条件：left = right = n，括号都用完了。
• 当left < n时，添加左括号，进入下一层递归。
• 当left >= n且left > right时，添加右括号，进入下一层递归。

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    var traversal = function(n, str, left, right){
        if(left == n && right == n){
            res.push(str);
            return;
        }
        if(left < n){
            traversal(n, str + "(", left + 1, right);
        }
        if(left > right){
            traversal(n, str + ")", left, right + 1);
        }
    };
    let res = [];
    traversal(n, "", 0, 0);
    return res;
};

68 单词搜索

• 回溯、DFS
• 遍历board中每一个格子，若该格子的字母为word的首字母，则开始进入dfs遍历。
• 进入dfs后，按照上、右、下、左四个方向遍历。
• 递归终止条件：找到了word的最后一个字母。
• 继续递归的条件：横纵坐标不越界、该坐标所在位置之前没有被访问过、该坐标对应的字母 = word中当前index对应的字母。

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    var dfs = function(board, word, vis, x, y, index){
        if(index == word.length){
            return true;
        }
        for(let d = 0; d < 4; d++){
            let x_ = x + dirt[d][0];
            let y_ = y + dirt[d][1];
            if(x_ >= 0 && x_ < m && y_ >= 0 && y_ < n && vis[x_][y_] == 0 && word[index] == board[x_][y_]){
                vis[x_][y_] = 1;
                if(dfs(board, word, vis, x_, y_, index + 1)){
                    return true;
                }
                vis[x_][y_] = 0;
            }
        }
        return false;
    };
    let m = board.length;
    let n = board[0].length;
    let vis = Array(m).fill(null).map(() => Array(n).fill(0));
    let dirt = [[1, 0], [0, 1], [-1, 0], [0, -1]];
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(word[0] == board[i][j]){
                vis[i][j] = 1;
                if(dfs(board, word, vis, i, j, 1)){
                    return true;
                }
                vis[i][j] = 0;
            } 
        }
    }
    return false;
};

69 分割回文串

• 回溯
• startIndex：从0开始，表示切割线。
• 判断当前切割的子串（ [ startIndex, i ] ）是否是回文字符串：双指针法，一前一后两个指针向中间移动。
• 递归终止条件：切割线到str最后了。
• 下一次递归的切割点：当前遍历字母的索引i + 1。

var isValid = function(str){
    let start = 0;
    let end = str.length - 1;
    while(start < end){
        if(str.charAt(start) != str.charAt(end)){
            return false;
        }
        start++;
        end--;
    }
    return true;
};

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    var traversal = function(s, startIndex){
        if(startIndex == s.length){
            res.push(path.slice());
            return;
        }
        for(let i = startIndex; i < s.length; i++){
            let tmp = s.slice(startIndex, i + 1);
            if(isValid(tmp)){
                path.push(tmp);
                traversal(s, i + 1);
                path.pop();
            }
        }
    }
    let res = [];
    let path = [];
    traversal(s, 0);
    return res;
};

70 N皇后

• 回溯
• row：遍历的行数，i：遍历的列数。
• 递归结束条件：最后一行放置完Q了，注意收集数组时应该转为字符串形式。

var isValid = function(chessboard, row, col, n){
    for (let i = 0; i < row; i++) {
      for (let j = 0; j < n; j++) {
        if (chessboard[i][j] == 'Q' && (j == col || Math.abs(i - row) == Math.abs(j - col))) {
          return false;
        }
      }
    }
    return true;
}

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    var traversal = function(chessboard, row, n){
        if(row == n){
            let tmp = chessboard.slice()
            for (let i = 0; i < n; i++) {
                tmp[i] = tmp[i].join(''); 
            }
            res.push(tmp);
            return;
        }
        for(let i = 0; i < n; i++){
            if(isValid(chessboard, row, i, n)){
                chessboard[row][i] = 'Q';
                traversal(chessboard, row + 1, n);
                chessboard[row][i] = '.';
            }
        }
    };
    let res = [];
    let chessboard = Array(n).fill(null).map(() => Array(n).fill('.'));
    traversal(chessboard, 0, n);
    return res;
};