# 回溯算法

# 思路

全局变量：保存结果
参数：递归函数的参数选择，通常是两种参数
1. 状态变量：result 需要保存的值
2. 条件变量：判断搜索是否完毕以及搜索是否合法
完成条件：完成条件是决定状态变量和条件变量取何值可以判断整个搜索流程结束。整个搜索流程结束有两个含义：搜索成功并保存结果和搜索失败并返回上一次状态。
递归过程：传递当前状态给下一次递归进行搜索

# 模版

let res = [] // 存储结果

function backtrack(path, condition, ...rest) {
  if(judge(condition)) { // 满足条件
    res.push(path)
    return
  }
  for(let select of selectList) {
    if(剪枝条件) break
    path.push(select) // 走某条路
    backtrack(path, newSelectList)
    path.pop() // 返回上一个十字路口
  }
}

# 适用场景

排列、组合
数组、字符串，给定一个特定的规则，尝试找到某个解
二维数组下的 DFS 搜索

# 题目

# 子集 (opens new window)

给定一组 不含重复元素 的整数数组 nums，返回该数组所有可能的子集（幂集）

# 思路

定义 res 数组存储结果
每个子集为状态变量，集合的元素个数为条件变量
子集的元素变量小于等于集合的元素数量为限制条件，满足条件时添加到结果数组，否则回退到上一步
下一层搜索的集合需要去掉一添加到状态变量中的元素

# 答案

function subsets(nums: number[]): number[][] {
  const res: number[][] = []
  const n = nums.length
  
  function back(path: number[], i: number): void {
    if(i <= n) res.push(path)
    for(let j = i; j < n; j++) {
      path.push(nums[j])
      back(path.slice(), j + 1)
      path.pop()
    }
  }
  
  back([], 0)
 
  return res
}

# 全排列 (opens new window)

给定一个 没有重复 数字的序列，返回其所有可能的全排列

# 思路

定义 res
每个排列序列为状态变量，排列序列中集合的个数为条件变量
当排列序列的元素等于给定序列时，满足条件
下一层递归依赖于上一层递归传递的路径

# 答案

function permute(nums: number[]): number[][] {
  const n = nums.length
  const res: number[][] = []
  
  function back(path: number[]): void {
    if(path.length === n) {
      res.push(path)
      return
    }
    
    for(let i = 0; i < n; i++) {
      if(!path.includes(nums[i])) {
        path.push(nums[i])
        back(path.slice())
        path.pop()
      }
    }
  }
  
  back([])
  
  return res
}

# 组合总数 (opens new window)

给定一个无重复元素的数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被使用。

# 思路

定义 res
每个子数组为状态变量，目标值为条件变量
子数组中的值相加等于目标变量则满足要求
下一层递归的 tar（与目标值相差的数目）依赖于上层递归的选择

# 答案

function combinationSum(candidates: number[], target: number): number[][] {
  const res: number[][] = []
	const n = candidates.length
  
  candidates.sort((a, b) => a - b) // 排序是为了防止在 for 循环 if 判断时直接跳出
  
  function back(path: number[], i: number, tar: number) {
    if(tar === 0) {
      res.push(path)
      return
    }
    
    for(let j = i; j < n; j++) {
      // 因为排序过，所以如果第一个元素比 tar 大，则之后的元素都会比 tar 大，所以可以直接跳出循环
      if(tar < candidates[j]) break 
      path.push(candidates[j])
      back(path.slice(), j, tar - candidates[j])
      path.pop()
    }
  }
  
  back([], 0, target)
  
  return res
}

# 分割回文串 (opens new window)

给定一个字符串 s，将 s 分割成一些子串，使得每个子串都是回文串。

返回 s 所有可能的分割方案。

# 思路

定义 res
状态变量为回文子串集，条件变量为子串集的字符串数目
当子串集的字符串数目与目标长度相同时，满足要求
下层递归的开始位置由上层递归决定

# 答案

function partition(s: string): string[][] {
  const res: string[][] = [];
  const n = s.length;

  function isPalindrome(s: string): boolean {
    let left = 0;
    let right = s.length - 1;
    while (left <= right) {
      if (s[left] !== s[right]) return false;
      left++;
      right--;
    }
    return true;
  }

  function back(path: string[], start: number): void {
    if (start === n) {
      res.push(path);
      return;
    }

    for (let i = start; i < n; i++) {
      if (!isPalindrome(s.slice(start, i + 1))) continue;
      path.push(s.slice(start, i + 1));
      back(path.slice(), i + 1);
      path.pop();
    }
  }

  back([], 0);
  return res;
}

# 单词搜索 (opens new window)

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻“单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

# 思路

状态变量为一条通路，条件变量为通路的长度
当通路与目标词汇长度一致时，满足条件
下一层递归的初始坐标和通路长度由上一层递归决定

# 答案

function exist(board: string[][], word: string): boolean {
  const rowNum = board.length;
  const colNum = board[0].length;

  for (let i = 0; i < rowNum; ++i) {
    for (let j = 0; j < colNum; ++j) {
      if (board[i][j] === word[0]) { // 从第一个字母开始匹配
        const isExist = back(word, i, j, {});
        if (isExist) return true;
      }
    }
  }

  function back(
    word: string,
    row: number,
    col: number,
    visited: { [key: string]: boolean }
  ): boolean {
    if (!word.length) return true; // 说明单词中字母全部匹配，可以返回true

    const key = `${row}-${col}`; // 越界、之前访问过的、单词首字母和元素不相同，返回false
    if (
      row >= board.length ||
      row < 0 ||
      col >= board[0].length ||
      col < 0 ||
      visited[key] ||
      board[row][col] !== word[0]
    ) {
      return false;
    }

    visited[key] = true;
    word = word.slice(1);

    const success = // 按顺序进行搜索
      back(word, row + 1, col, visited) ||
      back(word, row - 1, col, visited) ||
      back(word, row, col + 1, visited) ||
      back(word, row, col - 1, visited);
      
    visited[key] = success; // success 为 false 的时候就是回溯
    return success;
  }

  return false;
}

# 复原 IP 地址 (opens new window)

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 “.“ 分隔

# 思路

按顺序选择一个字符作为第一个片段
依次切割出四个整数，用 DFS 去遍历所有选择，一旦遇到不符合要求（整数大小为 0 到 255 之间）则进行回退

# 答案

function restoreIpAddresses(s: string): string[] {
  const res: string[] = [];

  function back(subRes: string[], start: number): void {
    if (subRes.length === 4 && start === s.length) {
      res.push(subRes.join("."));
      return;
    }
    if (subRes.length === 4 && start < s.length) return;
    for (let len = 1; len < 4; len++) {
      if (len - 1 + start >= s.length) return;
      if (len !== 1 && s[start] === "0") return;
      const str = s.substring(start, start + len);
      if (len === 3 && +str > 255) return;
      subRes.push(str);
      back(subRes, start + len);
      subRes.pop();
    }
  }

  back([], 0);

  return res;
}

← 哈希表.md 复杂度.md →