回溯算法

回溯法（back tracking）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯法对解空间做深度优先搜索时，有递归回溯和迭代回溯（非递归）两种方法，但一般情况下用递归方法实现回溯法。

letcode 回溯专题一看就懂，一写就懵？搞懂回溯算法，一口气刷了20多道题面试必备：回溯算法详解

从解决问题每一步的所有可能选项里系统选择出一个可行的解决方案。

在某一步选择一个选项后，进入下一步，然后面临新的选项。重复选择，直至达到最终状态。

排列组合

排列组合是组合数学中两个基本概念。它们涉及到对象的选择和排列方式，常常在概率论、组合优化、统计学等领域中应用广泛

排列Permutation

排列指的是从一组对象中按照一定的顺序选择若干个对象的方式。

在排列中，选取的对象是有序的，换句话说，排列考虑了元素之间的顺序。

比如，假设有三个不同的字母A、B、C，它们的所有不同排列是ABC、ACB、BAC、BCA、CAB、CBA。

一般来说，n个不同的对象进行排列，如果选择r个对象，有n个对象的排列数可以表示为P(n, r)，计算方式为n!/(n-r)!，其中n!表示n的阶乘，即n*(n-1)(n-2)...2*1。

下面是一种通过递归实现排列的实现。

function permutation(arr, r) {
    if (r === 0) return [[]]; // 当 r 为 0 时，返回空数组，表示选择完成
    if (arr.length === 0) return []; // 当 arr 数组为空时，返回空数组，表示无法再选择

    const result = [];
    arr.forEach((element, index) => {
        const rest = [...arr.slice(0, index), ...arr.slice(index + 1)]; // 移除当前元素
        const perms = permutation(rest, r - 1); // 对剩余元素进行 (r-1) 的排列
        perms.forEach(perm => {
            result.push([element, ...perm]); // 将当前元素与剩余元素的排列组合起来
        });
    });

    return result;
}

console.log("排列示例：", permutation(['A', 'B', 'C'], 2));
// [["A","B"],["A","C"],["B","A"],["B","C"],["C","A"],["C","B"]]

组合Combination

组合是从一组对象中选择若干个对象的方式，不考虑对象的顺序。在组合中，选取的对象是无序的。

比如，假设有三个不同的字母A、B、C，它们的所有不同组合是ABC、ACB、BAC、BCA、CAB、CBA。

一般来说，n个不同的对象进行组合，选择r个对象，有n个对象的组合数可以表示为C(n, r)，计算方式为n!/[(n-r)!*r!]，其中n!表示n的阶乘。


// 实现组合的函数
function combination(arr, r) {
    if (r === 0) return [[]]; // 当 r 为 0 时，返回空数组，表示选择完成
    if (arr.length === 0 || arr.length < r) return []; // 当 arr 数组为空，或者长度小于 r 时，返回空数组，表示无法再选择

    if (arr.length === r) return [arr]; // 当 arr 数组的长度等于 r 时，直接返回 arr，表示该组合就是所有元素

    const result = [];
    const rest = arr.slice(1); // 不选择第一个元素
    const withFirst = combination(rest, r - 1).map(comb => [arr[0], ...comb]); // 选择第一个元素，并在剩余元素中选择 (r-1) 个
    const withoutFirst = combination(rest, r); // 不选择第一个元素，在剩余元素中选择 r 个

    return result.concat(withFirst, withoutFirst);
}

console.log("组合示例：", combination(['A', 'B', 'C'], 2));
// [["A","B"],["A","C"],["B","C"]]

回溯算法 ​

排列组合 ​

排列Permutation ​

组合Combination ​

回溯算法

排列组合

排列Permutation

组合Combination