回溯算法

[Leo-lin214]

回溯算法，也叫试探法，通过遍历将每一种可能都走一遍，一旦遇到不符合结果的，就会回溯到上一层，再找另一子节点，以此类推，直到找到符合结果为止。

在生活里面，最常见莫过于迷宫找出路了，在一个分叉路口，当一条路发现不通后，就要回到分叉路口，接着找下一条路，以此类推。

可以看到，回溯算法可以说是穷举法，即把每一种可能都得查询一次，时间复杂度贼高。因此回溯算法常常需要结合剪枝来进行优化。

所谓剪枝，就是在遍历过程中将那些不符合结果的排除掉，具体看下面栗子就会很容易理解。

回溯算法代码段

从代码层面来看，回溯算法基本都是一个套路，先来看下：

const result = [];
const backTrack = (index, targetArr, tempArr) => {
  if (结束条件) {
    result.push([...tempArr]);
    return;
  }
  for (let i = 0; i < targetArr.length; i++) {
    // 剪枝行为
    // 选择当前元素
    tempArr.push(targetArr[i]);
    backTrack(i, targetArr, tempArr);
    // 撤销当前元素
    tempArr.pop();
  }
}

回溯算法的题目大体上可以分为三类：子集、组合和全排列。只要解决这三类问题，其实回溯算法就基本不是问题了。

子集 I

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

说明：结果里面不能包含重复的子集。

例如：nums = [1, 2, 3]，输出为：[1], [1, 2], [1, 3], [2], [2, 3], [3], [1, 2, 3], []

现在我们就来套用上面代码段。

const getChildSet = nums => {
  if (!nums || !Array.isArray(nums)) return null;
  const result = [];
  const backTrack = (index, targetArr, tempArr) => {
    result.push([...tempArr]);
    for (let i = 0; i < targetArr.length; i++) {
      tempArr.push(targetArr[i]);
      backTrack(i + 1, targetArr, tempArr);
      tempArr.pop();
    }
  }
  backTrack(0, nums, []);
  return result;
}

套用起来确实简单，但是当你去执行上面代码时，会发现栈溢出。

好明显，我们还没有做剪枝，接下来我们就来做剪枝操作。

const getChildSet = nums => {
  if (!nums || !Array.isArray(nums)) return null;
  const result = [];
  const backTrack = (index, targetArr, tempArr) => {
    result.push([...tempArr]);
    for (let i = index; i < targetArr.length; i++) {
      tempArr.push(targetArr[i]);
      backTrack(i + 1, targetArr, tempArr);
      tempArr.pop();
    }
  }
  backTrack(0, nums, []);
  return result;
}

只需要将 i 从 index 开始遍历即可，而前面遍历过的元素可以直接跳过，因为没必要再遍历。

子集 II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集。

说明：结果不能包含重复的子集。

例如：nums = [1, 2, 2]，结果为：[1], [1, 2], [1, 2, 2], [2], [2, 2], []

乍一看，跟上面意思是一样，不同点就在于对于 nums 中重复元素就不要再计算了，不然得到的结果是一样的。

const getChildSet = nums => {
  if (!nums || !Array.isArray(nums)) return null;
  nums.sort((a, b) => a - b);
  const result = [];
  const backTrack = (index, targetArr, tempArr) => {
    result.push([...tempArr]);
    for (let i = index; i < targetArr.length; i++) {
      if (i > index && targetArr[i] === targetArr[i - 1]) continue;
      tempArr.push(targetArr[i]);
      backTrack(i + 1, targetArr, tempArr);
      tempArr.pop();
    }
  }
  backTrack(0, nums, []);
  return result;
}

可以看到，比子集 I 多了两个，一个是先对数组进行排序，另一个则是判断元素是否已经遍历过，直接跳过。换句话说，排序就是为了让判断前后元素是否同一个，从而避免重复遍历。

而这也是剪枝，因此剪枝要根据实际情况进行剪。

组合总和 I

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

candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括 target）都是正整数。
• 结果不能包含重复的组合。

例如：candidates = [2, 3, 6, 7], target = 7, 输出为：[7], [2, 2, 3]

如果顺利理解上面子集问题后，那么组合问题就会变得很简单了，我接着套用代码段。

const getComposeSum = (candidates, target) => {
  if (!candidates || !Array.isArray(candidates)) return null;
  const result = [];
  const backTrack = (index, targetArr, tempArr, target) => {
    if (target === 0) {
      result.push([...tempArr]);
      return;
    }
		if (target < 0) return;
    for (let i = index; i < targetArr.length; i++) {
      tempArr.push(targetArr[i]);
      target -= targetArr[i];
      backTrack(i, targetArr, tempArr, target);
      target += targetArr[i];
      tempArr.pop();
    }
  }
  backTrack(0, candidates, [], target);
  return result;
}

组合总和 II

给定一个数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中每个数字再每个组合中只能使用一次。

说明：

• 所有数字（包括 target）都是正整数。
• 结果不能包含重复的组合。

例如：candidates = [10, 1, 2, 7, 6, 1, 5], target = 8，输出为：[1, 7], [1, 2, 5], [2, 6], [1, 1, 6]

明显比组合总和 II 中多了 candidates 是允许出现重复元素的，因此我们要剔除那些重复元素的遍历，避免重复遍历，跟子集 II 类似。

const getComposeSum = (candidates, target) => {
  if (!candidates || !Array.isArray(candidates)) return null;
  candidates.sort((a, b) => a - b);
  const result = [];
  const backTrack = (index, targetArr, tempArr, target) => {
    if (target === 0) {
      result.push([...tempArr]);
      return;
    }
    if (target < 0) return;
    for (let i = index; i < targetArr.length; i++) {
      if (i > index && targetArr[i] === targetArr[i - 1]) continue;
      tempArr.push(targetArr[i]);
      target -= targetArr[i];
      backTrack(i + 1, targetArr, tempArr, target);
      target += targetArr[i];
      tempArr.pop();
    }
  }
  backTrack(0, candidates, [], target);
  return result;
}

全排列 I

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

例如：nums = [1, 2, 3]，输出为：[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]

全排列的问题与前面的子集和组合是一个道理，将每一种情况都列举出来。

const getRange = nums => {
  if (!nums || !Array.isArray(nums)) return null;
  const result = [];
  const backTrack = (index, targetArr, tempArr) => {
    if (tempArr.length === targetArr.length) {
     	result.push([...tempArr]);
      return;
    }
    for (let i = 0; i < targetArr.length; i++) {
      if (tempArr.indexOf(targetArr[i]) > -1) continue;
      tempArr.push(targetArr[i]);
      backTrack(i + 1, targetArr, tempArr);
      tempArr.pop();
    }
  }
  backTrack(0, nums, []);
  return result;
}

全排列 II

给定一个可包含重复数字的序列 nums，返回所有不可重复的全排列。

例如：nums = [1, 1, 2]， 输出为：[1, 1, 2], [1, 2, 1], [2, 1, 1]。

由于 nums 中存在重复元素，因此使用全排列 I 中的方式是走不通的。

转个角度，我们可以使用另一个数组专门存储已经遍历过的元素，一旦该元素已经遍历过，直接跳过即可。

另外还需要考虑一个问题，对于重复元素，如果前面那个已经有结果了，那么需要去重处理，进而避免结果中出现重复集合。

const getRange = nums => {
  if (!nums || !Array.isArray(nums)) return null;
  nums.sort((a, b) => a - b);
  const result = [];
  const backTrack = (index, targetArr, tempArr, storage) => {
  	if (tempArr.length === targetArr.length) {
    	result.push([...tempArr]);
      return;
    }
    for (let i = 0; i < targetArr.length; i++) {
      if (storage[i]) continue;
      if (i > 0 && targetArr[i] === targetArr[i - 1] && storage[i - 1]) break;
      tempArr.push(targetArr[i]);
      storage[i] = targetArr[i];
      backTrack(i + 1, targetArr, tempArr, storage);
      storage[i] = undefined;
      tempArr.pop();
    }
  }
  backTrack(0, nums, [], []);
  return result;
}

回溯算法相比前面的动态规划和贪心算法都好理解，基本都是在三大类型题目上---子集、组合、排列。

直接套用代码段，但是需要考虑好剪枝问题，根据实际情况进行剪枝。