算法：回溯算法

发表于 | 分类于

回溯算法

暴力求解！列出所有，根据需要剪枝！

  • 适合由多个步骤组成的问题，并且每个步骤都有多个选项
  • 从某一步的所有可能选项里选择出一个可行方案，不满足约束条件，回溯到上一步，尝试其他选项
  • 所有状态均不满足，无解

全排列

  • input: [1,2,3]
  • output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    思路：
  1. 第一位有3位选择，选1，第二位就只能选2或3，如果选2，则第三位只能选3；再回到第二位，选3，则第三位只能选2；接着回到第一位，之前选了1，现在选2，然后继续…
  2. 每一种排列看作一条路径，递归
  3. 递归的入口，path空数组；递归的出口，path的长度等于nums长度，代表选满，生成了一个排列，可以推入结果数组
  4. 遍历nums数组，如果当前数字已经推入过数组，则不推入，继续考察下一个数字，否则，推入path，并且递归调用dfs，继续选下一个数字，直到选满
  5. path.pop()回溯，path的最后一个选择被撤销，回到之前的状态，继续下一个迭代，考察上一层的别的选择
  6. 用一个map记录已经加入路径的数字，避免调用includes导致O(n)的查找时间
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    const permute = (nums) => {
      const res = [];
      const used = {};
      dfs([]);
      function dfs(path) {
        if(path.length == nums.length) {
          res.push(path.slice());
          return;
        }
        for(const num of nums) {
          if(used[num]) continue;
          path.push(num);
          used[num] = true;
          dfs(path);
          path.pop();
          used[num] = false;
        }
      }
      return res;
    }

组合

  • 1到n中所有可能的k个数的组合
  • input: n = 4, k = 2
  • [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
    思路：
  1. 第一位有4个选择，选出第一位再选第二位时候，为避免和之前出现重复选择，要修建掉一些选择
  2. 使得下一个选择的遍历起点，是当前选择的数字+1
  3. 利用path作为路径，当path中的数字达到k时候，就加入结果数组
  4. 遇到完整解的时候，结束当前搜索分支，继续去搜索下一个分支
  5. 撤销最后一个选择，回到选择前的状态，尝试另一个选择
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    const combine = (n, k) => {
      const res = [];
      const helper = (start, path) => {
        if (path.length == k) {
          res.push(path.slice());
          return;
        }
        for(let i = start; i<=n; i++) {
          path.push(i);
          helper(i+1, path);
          path.pop();
        }
      }
      helper(1,[]);
      return res;
    }

组合总和

  • 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
  • candidates = [2,3,6,7], target = 7
思路
  1. 递归：当sum大于或者等于target的时候结束这次递归
  2. 在递归中遍历可选择项时候，控制遍历的起点，避免[2,2,3]和[2,3,2]这种重复
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const combinationSum = (candidates, target) => {
  const res = [];
  const dfs = (start, temp, sum) => {
    if (sum >= target) {
      if (sum == target) {
        res.push(temp.slice());
      }
      return;
    }
    for(let i = start; i < candidates.length; i++) {
      temp.push(candidates[i]);
      dfs(i, temp, sum+candidates[i]);
      temp.pop();
    }
  };
  dfs(0,[],0);
  return res;
}

子集

  • input: nums=[1,2,3]
  • output: [[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var subsets = function(nums) {
    const res = [];
    dfs([],0);
    function dfs(path,start) {
        if(path.length > nums.length) {
            return;
        }
        res.push(path.slice());
        for(let i=start;i<nums.length;i++) {
            path.push(nums[i])
            dfs(path,i+1);
            path.pop();
        }
    }
    return res;
};

有重复的子集

  • input: [1,2,2]
  • output: [[2],[1],[1,2,2],[2,2],[1,2],[]]
  • 和 上一个相比，去重的方式：排序后用indexof或者排序后和i-1的那个比较
    indexof去重
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    var subsetsWithDup = function(nums) {
        nums.sort();
        const res = [];
        dfs([],0);
        function dfs (path,start) {
            if(path.length > nums.length || JSON.stringify(res).indexOf(JSON.stringify(path))>0) {
                return;
            }
            res.push(path.slice());
            for(let i=start;i<nums.length;i++) {
                path.push(nums[i]);
                dfs(path, i+1);
                path.pop();
            }
        }
        return res
    };
排序后和i-1比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var subsetsWithDup = function(nums) {
    nums.sort();
    const res = [];
    dfs([],0);
    function dfs (path,start) {
        if(path.length > nums.length) {
            return;
        }
        res.push(path.slice());
        for(let i=start;i<nums.length;i++) {
            if(nums[i] == nums[i-1] && i-1 >=start) continue;
            path.push(nums[i]);
            dfs(path, i+1);
            path.pop();
        }
    }
    return res
};

二叉树中和为某一个值的路径

思路
  1. 从根节点开始深度优先遍历，每经过一个节点，将节点入栈
  2. 到达叶子节点，且当前路径之和等于给定目标值，则找到一个可行的解决方案，将其加入结果数组
  3. 遍历到达二叉树的某个节点时有2个可能的选项，选择前往左子树或右子树
  4. 若存在左子树，继续向左子树递归
  5. 若存在右子树，继续向右子树递归
  6. 若上述条件均不满足，或已经遍历过，将当前节点出栈，向上回溯。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    function FindPath(root, expectNumber)
    {
      const result = [];
      if(root){
        FindPathCore(root,expectNumber,[],0,result);
      }
      return result;
    }
    function FindPathCore(node,num,stack,sum,result){
      stack.push(node.val);
      sum += node.val;
      if(!node.left && !node.right && sum===num){
        result.push(stack.slice(0));
      }
      if(node.left){
        FindPathCore(node.left,num,stack,sum,result);
      }
      if(node.right){
        FindPathCore(node.right,num,stack,sum,result);
      }
      stack.pop();
    }