回溯算法

关于回溯算法这里推荐阅读 C++ 总结了回溯问题类型 带你搞懂回溯算法(大量例题) (opens new window) 这篇文章。

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来换一条路再试。 — LeetCode

回溯算法是建立在 DFS 上的，DFS 是一条道跑到黑；回溯算法是结束条件后，恢复状态，回溯上一层，再次搜索。回溯算法和 DFS 的区别就是有无状态重置。

什么时候使用回溯算法呢？当满足条件或者发现不是正确路径的时候，要撤销选择回退到上一个状态，继续尝试时，需要考虑回溯算法。

全排列问题

题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。

示例：   
输入: [1,2,3]
输出: [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/VvJkup
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

全排列

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列

function permute(nums) {
  const len = nums.length, curr = [], res = [], used = {};
  function dfs(nth) {
    if (nth === len) return res.push(curr.slice())
    nums.forEach(item => {
      if (!used[item]) {
        used[item] = true
        curr.push(item)
        dfs(nth + 1)
        curr.pop()
        used[item] = false
      }
    })
  }
  dfs(0)
  return res
}

console.log(permute([1, 2, 3]))

给定任意二维数组，输出所有的排列组合项。

比如 [['A','B'], ['a','b'], [1, 2]]

输出 ['Aa1','Aa2','Ab1','Ab2','Ba1','Ba2','Bb1','Bb2']

function permutate(arr) {
    const res = [];
    function dfs(str, arr) {
        if (arr.length === 0){
            res.push(str);
            return;
        }
        const [ head, ...values ] = arr;
        for (let i = 0, len = head.length; i < len; i++) {
            dfs(str+head[i], values);
        }
    }
    dfs('',arr);
    return res;
}

/**
 * 动态规划，下一次的结果，依赖上一次的结果
 * @param {array} arr 
 */
function permutate(arr) {
    // 第一次的结果就是二维数组的第0项
	let res = arr[0].slice();

	for (let i = 1; i < arr.length; i++) {
		const pre = res.slice();
		res = [];
		pre.forEach(item => {
			arr[i].forEach(curr => {
				res.push(item + curr)
			})
		});
	}
	console.log(res)
	return res;
}

作者：pbxrt
链接：https://juejin.cn/post/6862585470375690253
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

组合问题

题目描述：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

示例: 输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

限定组合问题：及时回溯，即为“剪枝”

题目描述：给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combinations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题模板

function xxx(入参) {
  前期的变量定义、缓存等准备工作 
  
  // 定义路径栈
  const path = []
  
  // 进入 dfs
  dfs(起点) 
  
  // 定义 dfs
  dfs(递归参数) {
    if(到达了递归边界) {
      结合题意处理边界逻辑，往往和 path 内容有关
      return   
    }
    
    // 注意这里也可能不是 for，视题意决定
    for(遍历坑位的可选值) {
      path.push(当前选中值)
      处理坑位本身的相关逻辑
      path.pop()
    }
  }
}

当一个题目设计到穷举的时候可以尝试下上面的解题模板。