回溯法（DFS）

子集、组合、排列

解决一个回溯问题，实际上就是一个决策树的遍历过程

元素无重不可复选

元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次

  1. /* 组合/子集问题回溯算法框架 */
  2. void backtrack(int[] nums, int start) {
  3.     // 回溯算法标准框架
  4.     for (int i = start; i < nums.length; i++) {
  5.         // 做选择
  6.         track.addLast(nums[i]);
  7.         // 注意参数
  8.         backtrack(nums, i + 1);
  9.         // 撤销选择
  10.         track.removeLast();
  11.     }
  12. }
  14. /* 排列问题回溯算法框架 */
  15. let res = []
  16. let used = [] // 记录是否已选择
  17. void backtrack(int[] nums) {
  18.     for (int i = 0; i < nums.length; i++) {
  19.         // 剪枝逻辑
  20.         if (used[i]) {
  21.             continue;
  22.         }
  23.         // 做选择
  24.         used[i] = true;
  25.         track.addLast(nums[i]);
  27.         backtrack(nums);
  28.         // 撤销选择
  29.         track.removeLast();
  30.         used[i] = false;
  31.     }
  32. }

78. 子集

  1. // 用一个 start 排除 start 索引之前的数字
  2. var subsets = function(nums) {
  3.   let res = []
  4.   const backTrack = (nums, track = [], startIndex = 0) => {
  5.     res.push(track)
  6.     for (let i = startIndex; i < nums.length; i ++) {
  7.       track.push(nums[i])
  8.       backTrack(nums, [...track], i + 1)
  9.       track.pop()
  10.     }
  11.   }
  12.   backTrack(nums, [], 0)
  13.   return res
  14. }

77.组合

  1. var combine = function(n, k) {
  2.   let res = []
  3.   const backTrack = (n, track = [], startIndex = 1) => {
  4.     if (track.length === k) {
  5.       res.push(track)
  6.     }
  7.     for (let i = startIndex; i <= n; i ++) {
  8.       track.push(i)
  9.       backTrack(n, [...track], i + 1)
  10.       track.pop()
  11.     }
  12.   }
  13.   backTrack(n, [], 1)
  14.   return res
  15. }

46.全排列

  1. var permute = function(nums) {
  2.   let res = []
  3.   let used = []
  4.   const backTrack = (nums, track = []) => {
  5.     if (track.length === nums.length) {
  6.       res.push(track)
  7.     }
  8.     for (let i = 0; i < nums.length; i ++) {
  9.       if (used[i]) {
  10.         continue
  11.       }
  12.       if (i > 0 && nums[i - 1] === nums[i] && used[i - 1]) {
  13.         continue
  14.       }
  15.       used[i] = true
  16.       track.push(nums[i])
  17.       backTrack(nums, [...track])
  18.       track.pop()
  19.       used[i] = false
  20.     }
  21.   }
  22.   backTrack(nums, [])
  23.   return res
  24. };

元素可重不可复选

元素可重不可复选，即 **nums** 中的元素可以存在重复，每个元素最多只能被使用一次，其关键在于排序和剪枝

  1. /* 组合/子集问题回溯算法框架 */
  2. Arrays.sort(nums); // 排序
  3. void backtrack(int[] nums, int start) {
  4.     // 回溯算法标准框架
  5.     for (int i = start; i < nums.length; i++) {
  6.         // 剪枝逻辑，跳过值相同的相邻树枝
  7.         if (i > start && nums[i] == nums[i - 1]) {
  8.             continue;
  9.         }
  10.         // 做选择
  11.         track.addLast(nums[i]);
  12.         // 注意参数
  13.         backtrack(nums, i + 1);
  14.         // 撤销选择
  15.         track.removeLast();
  16.     }
  17. }
  21. /* 排列问题回溯算法框架 */
  22. let used = []
  23. Arrays.sort(nums); // 排序
  24. void backtrack(int[] nums) {
  25.     for (int i = 0; i < nums.length; i++) {
  26.         // 剪枝逻辑
  27.         if (used[i]) {
  28.             continue;
  29.         }
  30.         // 剪枝逻辑，固定相同的元素在排列中的相对位置
  31.         if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
  32.             continue;
  33.         }
  34.         // 做选择
  35.         used[i] = true;
  36.         track.addLast(nums[i]);
  38.         backtrack(nums);
  39.         // 撤销选择
  40.         track.removeLast();
  41.         used[i] = false;
  42.     }
  43. }

47.全排列II

  1. var permuteUnique = function(nums) {
  2.   let res = []
  3.   let used = []
  4.   // 对 nums 进行了排序
  5.   nums.sort((a, b) => a - b)
  6.   const backTrack = (nums, track = []) => {
  7.     if (track.length === nums.length) {
  8.       res.push(track)
  9.     }
  10.     for (let i = 0; i < nums.length; i ++) {
  11.       if (used[i]) {
  12.         continue
  13.       }
  14.       // 剪枝
  15.       if (i > 0 && nums[i - 1] === nums[i] && used[i - 1]) {
  16.         continue
  17.       }
  18.       used[i] = true
  19.       track.push(nums[i])
  20.       backTrack(nums, [...track])
  21.       track.pop()
  22.       used[i] = false
  23.     }
  24.   }
  25.   backTrack(nums, [])
  26.   return res
  27. };

90. 子集 II

需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过

var subsetsWithDup = function(nums) {
  // 先排序，让相同的元素靠在一起
  nums = nums.sort((a, b) => a - b)
  let res = []
  const backTrack = (nums, track = [], startIndex = 0) => {
    res.push(track)
    for (let i = startIndex; i < nums.length; i ++) {
      // 剪枝逻辑，值相同的相邻树枝，只遍历第一条
      if (i > startIndex && nums[i] === nums[i - 1]) {
        continue
      }
      track.push(nums[i])
      backTrack(nums, [...track], i + 1)
      track.pop()
    }
  }
  backTrack(nums, [], 0)
  return res
};

组合总和 II

var combinationSum2 = function(candidates, target) {
  candidates = candidates.sort((a, b) => a - b)
  let res = []
  let trackSum = 0
  const backTrack = (candidates, track = [], startIndex = 0) => {
    // base case，超过目标和，直接结束
    if (trackSum > target) {
        return;
    }
    // 存入结果
    if (trackSum === target) {
      res.push(track)
    }
    for (let i = startIndex; i < candidates.length; i ++) {
      if (i > startIndex && candidates[i] === candidates[i - 1]) {
        continue
      }
      track.push(candidates[i])
      trackSum += candidates[i]
      backTrack(candidates, [...track], i + 1)
      track.pop()
      trackSum -= candidates[i]
    }
  }
  backTrack(candidates, [], 0)
  return res
};

元素无重可复选

形式三、元素无重可复选，即 **nums** 中的元素都是唯一的，每个元素可以被使用若干次，只要删掉去重逻辑即可

/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i);
        // 撤销选择
        track.removeLast();
    }
}


/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        backtrack(nums);
        // 撤销选择
        track.removeLast();
    }
}

39. 组合总和

var combinationSum = function(candidates, target) {
  let res = []
  let trackSum = 0
  const backTrack = (candidates, track = [], startIndex = 0) => {
    if (trackSum === target) {
      res.push(track)
    }
    if (trackSum > target) {
      return
    }
    for (let i = startIndex; i < candidates.length; i ++) {
      if (i > 0 && candidates[i - 1] === candidates[i]) {
        continue
      }
      track.push(candidates[i])
      trackSum += candidates[i]
      backTrack(candidates, [...track], i)
      track.pop()
      trackSum -= candidates[i]
    }
  }
  backTrack(candidates, [], 0)
  return res
};

回溯法最佳实践

51.N 皇后

/**
 * 这里生成棋盘时不直接创建['....', '....']形式的棋盘是因为JS中不能直接对字符串的某位进行替换
 * 当然也可以直接创建, board[row][col] = 'Q' 需要通过字符串的substring 和 replace方法实现 较为繁琐
 */
var solveNQueens = function(n) {
  // 生成棋盘 n x n
  const emptyBoard = new Array(n).fill(0).map(_ => Array(n).fill('.'))
  // 是否能放置皇后
  const isValid = (board, row, col) => {
    for (let i = 0; i < n; i ++) {
      if (board[i][col] === 'Q') return false
    }
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i --, j ++) {
      if (board[i][j] === 'Q') return false
    }
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i --, j --) {
      if (board[i][j] === 'Q') return false
    }
    return true
  }
  // 按行回溯
  const backTrack = (board, row = 0) => {
    // 遍历到最后一行，皇后已摆放完毕，棋盘以【字符串】形式存入结果
    if (row === n) {
      const validBoard = board.map(i => i.join(''))
      res.push(validBoard)
      return
    }
    // 回溯模板
    for (let col = 0; col < n; col ++) {
      if (isValid(board, row, col)) {
        board[row][col] = 'Q'
        backTrack(board, row + 1)
        board[row][col] = '.'
      }
    }
  }
  let res = []
  backTrack(emptyBoard, 0)
  return res
};

37. 解数独

var solveSudoku = function(board) {
  const isValid = (board, row, col, n) => {
    for (let i = 0; i < 9; i ++) {
      const R = Math.floor(row / 3) * 3 + Math.floor(i / 3)
      const C = Math.floor(col / 3) * 3 + Math.floor(i % 3)
      // 行是否重复
      if (board[row][i] === n) {
        return false
      }
      // 列是否重复
      if (board[i][col] === n) {
        return false
      }
      // 判断 3 x 3 小块是否存在重复
      if (board[R][C] === n) {
          return false
      }
    }
    return true
  }
  const backTrack = (board, row, col) => {
    // 到列尾，换下一行
    if (col === 9) {
      return backTrack(board, row + 1, 0)
    }
    // 到达最后一行，返回结果
    if (row === 9) {
      return true
    }
    // 跳过预设数字
    if (board[row][col] !== '.') {
      return backTrack(board, row, col + 1)
    }
    // 回溯模板
    for (let i = 1; i <= 9; i ++) {
      const ch = i.toString()
      if (isValid(board, row, col, ch)) {
        board[row][col] = ch
        if (backTrack(board, row, col + 1)) {
          return true
        }
        board[row][col] = '.'
      }
    }
    return false
  }
  if (backTrack(board, 0, 0)) {
    return board
  }
};

22. 括号生成

var generateParenthesis = function(n) {
  let res = []
  const backTrack = (left = n, right = n, track = []) => {
    // baseCase1: 合法的括号一定先用左括号
    if (right < left) {
      return 
    }
    // baseCase2: 合法的括号左右括号刚好一起用完
    if (left < 0 || right < 0) {
      return
    }
    if (left === 0 && right === 0) {
      res.push(track.join(''))
    }
    for (let item of ['(', ')']) {
      track.push(item)
      item === '(' && backTrack(left - 1, right, [...track])
      item === ')' && backTrack(left, right - 1, [...track])
      track.pop()
    }
  }
  backTrack(n, n, [])
  return res
};