leetcode-回溯

一、模板

1. 经典回溯通用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/** 
 * 经典回溯通用模板
 */

var problem = (data) => {
  // 0. prepare
  const res = []
  dfs(data, 0, "") // cur_state: "" / []
  return res

  function dfs (data, level, cur_state) {
    // 1. terminator
    if (level === data.length) {
      // notice: every level should not affect each other.
      res.push(cur_state) // [].slice() 
      return
    }

    // 2. process logic in current level
    // 2.1 no pick logic
    // 2.2 pick logic

    // 3. drill down

    // 4. reverse
    // return ...
  }
}

2. 二维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/** 二维 */
var problem = (board, target) => {
  // 0. prepare
  const dx = [-1, 0, 1, 0] // ↑→↓←
  const dy = [0, 1, 0, -1] // ↑→↓←
  const rows = board.length // 行
  const cols = board[0].length  // 列
  const visited = new Array(rows) // 记录是否已访问
    .fill(0)
    .map(() => new Array(cols).fill(false))

  function inArea(x, y) {
    return x >= 0 && x < rows && y >= 0 && y < cols
  }

  for (let i = 0; i < rows; i++)
    for (let j = 0; j < cols; j++)
      if (dfs(board, target, 0, i, j))
        return true
  return false

  function dfs (board, target, level, x, y) {
    // 1. terminator
    if (level === target.length - 1)
      return board[x][y] === target[level]

    // 2. current login in current level
    // 2.1 not pick
    if (board[x][y] !== word[level]) 
      return false

    // 2.2 pick
    visited[x][y] = true
    for (let i = 0; i < 4; i++) {
      const newX = x + dx[i]
      const newY = y + dy[i]

      // 3. drill down
      if (inArea(newX, newY) 
          && !visited[newX][newY] 
          && dfs(board, word, level + 1, newX, newY)
         )
        return true
    }
    // 4.reverse
    visited[x][y] = false
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/** floodfill */
var problem = function (grid) {
  // 0. prepare
  const dx = [-1, 0, 1, 0] // ↑→↓←
  const dy = [0, 1, 0, -1] // ↑→↓←
  const rows = board.length // 行
  const cols = board[0].length  // 列
  const visited = new Array(rows) // 记录是否已访问
    .fill(0)
    .map(() => new Array(cols).fill(false))

  function inArea(x, y) {
    return x >= 0 && x < rows && y >= 0 && y < cols
  }

  let res = 0
  for (let i = 0; i < rows; i++)
    for (let j = 0; j < cols; j++)
      if (grid[i][j] === '1' && !visited[i][j]){
        res++
        dfs(grid,i,j)
      }
  return res

  function dfs (grid, x, y) {
    // 1. process logic
    visited[x][y] = true

    for (let i = 0; i < 4; i++) {
      const newX = x + dx[i]
      const newY = y + dy[i]
      // 2. terminator and drill down
      if (
        inArea(newX, newY) 
        && !visited[newX][newY] 
        && grid[newX][newY] === '1'
      )
        dfs(grid, newX, newY)
    }
  }
}

二、题目

(1) 树形问题

22. 括号生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var generateParenthesis = function(n) {
  let res = []
  if(n === 0) return res
  _gengerate(n,0,0,"")
  return res

  function _gengerate(n,left,right,s){
    if(left === n && right === n){
      res.push(s)
      return
    }

    if(left < n) _gengerate(n,left+1,right,s+'(')
    if(right < left) _gengerate(n,left,right+1,s+')')
  }
};

17. 电话号码的字母组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var letterCombinations = function (digits) {
   const res = []
  const letters = [" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
  if (digits.length === 0)
    return res
  dfs(digits, 0, "")
  return res

  function dfs(digits, index, cur) {
    if (digits.length === index) {
      res.push(cur)
      return
    }

    const c = digits[index]
    const curLetters = letters[c.charCodeAt() - '0'.charCodeAt()]
    for (let i = 0; i < curLetters.length; i++) {
      dfs(digits, index + 1, cur + curLetters[i])
    }
  }
};

(2) 排列问题

46. 全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var permute = function (nums) {
  const res = []
  const used = new Array(nums.length).fill(false)
  if (nums.length === 0)
    return res
  dfs(nums, 0, [])
  return res

  function dfs(nums, index, p) {
    if (nums.length === index) {
      res.push(p.slice())
      return
    }

    for (let i = 0; i < nums.length; i++) {
      if (!used[i]) {
        p.push(nums[i])
        used[i] = true

        dfs(nums, index + 1, p)

        p.pop()
        used[i] = false
      }
    }
  }
};

47. 全排列 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var permuteUnique = function(nums) {
  const used = new Array(nums.length).fill(false)
  nums.sort((a,b)=>a-b) // 先排序
  const res = []
  dfs(nums,0,[])
  return res

  function dfs(nums,index,p){
    if(index === nums.length){
      res.push(p.slice())
      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

      used[i] = true
      p.push(nums[i])

      dfs(nums,index+1,p)

      used[i] = false
      p.pop(nums[i])
    }
    return
  }
};

(3) 组合问题

77. 组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var combine = function(n, k) {
  const res = []
  if (n <= 0 || k <= 0 || k > n)
    return res
  dfs(n, k, 1, [])
  return res

  function dfs(n, k, start, p) {
    if (p.length === k) {
      res.push(p.slice())
      return
    }
    
    // for (let i = start; i <= n; i++) {
    for (let i = start; i <= n - (k - p.length) + 1; i++) { // // 优化
      p.push(i)
      dfs(n, k, i + 1, p)
      p.pop()
    }
    
    return
  }
};

(4) 子集问题

78. 子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 回溯
var subsets = function(nums) {
  const res = []
  if(nums.length === 0) return res
  dfs(0,[])
  return res

  function dfs(index,list){
    if(index === nums.length){
      res.push(list.slice())
      return
    }

    dfs(index+1,list) // no pick
    list.push(nums[index])
    dfs(index+1,list) // pick
    list.pop()
  }
};

// 迭代
var subsets = function(nums) {
  const res = [[]]
  for(let num of nums){
    let len = res.length
    for(let j = 0;j<len;j++){
      const temp = [...res[j]]
      temp.push(num)
      res.push(temp)
    }
  }
  return res
};

(5) 二维问题

79. 单词搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
var exist = function (board, word) {
  const dx = [-1, 0, 1, 0] // ↑→↓←
  const dy = [0, 1, 0, -1] // ↑→↓←
  const rows = board.length
  const cols = board[0].length
  const visited = new Array(rows)
    .fill('')
    .map(() => new Array(cols).fill(false))

  function inArea(x, y) {
    return x >= 0 && x < rows && y >= 0 && y < cols
  }

  for (let i = 0; i < rows; i++)
    for (let j = 0; j < cols; j++)
      if (searchWord(board, word, 0, i, j))
        return true
  return false

  function searchWord(board, word, index, x, y) {
    if (word.length - 1 === index) {
      return board[x][y] === word[index]
    }

    if (board[x][y] !== word[index])
      return false

    visited[x][y] = true
    for (let i = 0; i < 4; i++) {
      const newX = x + dx[i]
      const newY = y + dy[i]
      if (
        inArea(newX, newY)
        && !visited[newX][newY]
        && searchWord(board, word, index + 1, newX, newY)
      )
        return true
    }
    visited[x][y] = false
  }
};

200. 岛屿数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var numIslands = function (grid) {
  const dx = [-1, 0, 1, 0]
  const dy = [0, 1, 0, -1]
  const rows = grid.length
  const cols = grid[0].length
  const visited = new Array(rows)
    .fill(0)
    .map(() => new Array(cols).fill(false))

  function inArea(x, y) {
    return x >= 0 && x < rows && y >= 0 && y < cols
  }

  let res = 0
  for (let i = 0; i < rows; i++)
    for (let j = 0; j < cols; j++)
      if (grid[i][j] === '1' && !visited[i][j]){
        res++
        dfs(grid, i, j)
      }
  return res

  function dfs(grid, x, y) {
    visited[x][y] = true
    for (let i = 0; i < 4; i++) {
      const newX = x + dx[i]
      const newY = y + dy[i]
      if (
        inArea(newX, newY)
        && !visited[newX][newY]
        && grid[newX][newY] === '1'
      )
        dfs(grid,newX,newY)
    }
  }
};

51. N 皇后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
var solveNQueens = function (n) {
  let res = []

  // 记录第i列是否已放置
  const cols = new Array(n).fill(false)
  // 记录 / 对角线是否已放置(共2*n-1个对角线)  row+col=0,1,2...
  const pie = new Array(2 * n - 1).fill(false)
  // 记录 \ 对角线是否已放置(共2*n-1个对角线)  row-col+n-1
  const na = new Array(2 * n - 1).fill(false)

  dfs(n, 0, [])
  return res

  // 在n皇后问题中，尝试在index行摆放皇后
  function dfs (n, row, cur_res) {
    if (row === n) {
      res.push(generateBoard(n, cur_res))
      return
    }

    // 遍历列，尝试摆放
    for (let col = 0; col < n; col++) {
      if (!cols[col] && !pie[row + col] && !na[row - col + n - 1]) {

        cur_res.push(col)
        cols[col] = true
        pie[row + col] = true
        na[row - col + n - 1] = true

        dfs(n, row + 1, cur_res)

        cols[col] = false
        pie[row + col] = false
        na[row - col + n - 1] = false
        cur_res.pop()
      }
    }
    return
  }

  // 打印n皇后的一个解
  function generateBoard (n, rows) {
    const board = new Array(n).fill('.'.repeat(n))
    for (let i = 0; i < n; i++) {
      let arr = board[i].split('')
      arr[rows[i]] = 'Q'
      board[i] = arr.join('')
    }
    return board
  }
  /*
  function generateBoard (n, rows) {
    return new Array(n)
      .fill("")
      .map((_, index) => '.'.repeat(rows[index]) + 'Q' + '.'.repeat(n - rows[index] - 1))
  }
  */
}

52. N皇后 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
var totalNQueens = function(n) {
  let res = 0
  // 记录第i列是否已放置
  const col = new Array(n).fill(false)
  // 记录 / 对角线是否已放置
  const dia1 = new Array(2 * n - 1).fill(false)
  // 记录 \ 对角线是否已放置
  const dia2 = new Array(2 * n - 1).fill(false)

  // 在n皇后问题中，尝试在index行摆放皇后
  const putQueue = (n, index, row) => {
    if (index === n) {
      res++
      return
    }

    // 遍历列，尝试摆放
    for (let i = 0; i < n; i++) {
      if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {
        row.push(i)
        col[i] = true
        dia1[index + i] = true
        dia2[index - i + n - 1] = true
        putQueue(n, index + 1, row)
        col[i] = false
        dia1[index + i] = false
        dia2[index - i + n - 1] = false
        row.pop()
      }
    }

    return
  }

  putQueue(n, 0, [])

  return res
};

// TODO:

  • [ ] 93
  • [ ] 131
  • [ ] 39
  • [ ] 40
  • [ ] 216
  • [ ] 90
  • [ ] 401
  • [ ] 130
  • [ ] 417
  • [ ] 37