Day27:Backtracking -回溯法

回溯法是暴力破解法的一种，在列出各种可能的组合时，如果遇到不符合条件的就不再继续向下查找，而是回到上层继续寻找其他可能，听起来有点抽象，可以想像有很多条岔路可以做选择，不过已经知道有些岔路不会得到我们需要的结果，就没有必要继续往下找，而是折返到上个路口，继续探索其他还没访问过的岔路，如同下图所示

图片来源:backtracking-introduction

在理解回溯法之前需要先认识permutation排列法

甚麽是permutation排列法?

是将相异物件或符号根据确定的顺序重排。每个顺序都称作一个置换或排列。例如，从一到六的数字有720种排列，对应於由这些数字组成的所有不重复亦不阙漏的序列，例如"4, 5, 6, 1, 2, 3" 与1, 3, 5, 2, 4, 6。(引用自wikipedia)

假设现在有个字串ABC，试问会有几种排列组合? 所有可能的排列组合如下图，可以推论出公式 = 阶乘
Ex.字串长度为3的话，就会有3*2*1=6种可能

用js实作

const arr = ["A", "B", "C"];

const permutation = (arr) => {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            for (let k = 0; k < arr.length; k++) {
                if (i === j || j === k || k === i) {
                    continue;
                }
                console.log(arr[i], arr[j], arr[k]);
            }
        }
    }
};

permutation(arr);
//A B C
//A C B
//B A C
//B C A
//C A B
//C B A

利用三个回圈列出所有排列组合，假设字串当中任意两个单字相同，就排除掉该组合，将程序流程画成图的话，会发现紫色三角形的范围其实全部都不符合条件，(非ABC的排列组合)

因此在i=0, j=0的时候就要喊停了，回溯到i=0这一个步骤，这个中断向下查找往回走的动作就是Backtracking

提早设定中止条件，向上回溯的程序码如下

const arr = ["A", "B", "C"];
const permutation = (arr) => {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (i === j) {
                continue;
            }
            for (let k = 0; k < arr.length; k++) {
                if (j === k || k === i) {
                    continue;
                }
                console.log(arr[i], arr[j], arr[k]);
            }
        }
    }
};

permutation(arr);

尝试用双指针的概念来解这题，利用start与i两个指针互换位置来取得不同的排列组合，执行的步骤如下

start跟i都从0开始

start=0，i=0，获得以A为开头的组合，ex. ABC

i前进一格之後与start交换位置

start=0，i=1，获得以B为开头的组合，ex. BAC

i前进一格之後与start交换位置

start=0，i=2，获得以C为开头的组合，ex. CBA

当i=2的时候意谓着i指针已经走到最後一步，这时start指针必须前进一步，i指针则退回与start指针相同的位置，依循先前的规则，start和i两个指针所指向的字母作交换，交换完毕後 i+1

字串ABC

start=1，i=1，两个指针指向同个字母，交换後维持不变，依然是ABC
start=1，i=2，两个指针互换後，获得ACB

字串BAC

start=1，i=1，两个指针指向同个字母，交换後维持不变，依然是BAC
start=1，i=2，两个指针互换後，获得BCA

字串CBA

start=1，i=1，两个指针指向同个字母，交换後维持不变，依然是CBA
start=1，i=2，两个指针互换後，获得CAB

用js实作

let result = [];
const permutation = (arr, start) => {
    if (start >= arr.length) {
        //因为arr最後会被换回原本的字串ABC 需要用浅拷贝的方式复制当下已经交换过的阵列 
        result.push([...arr]);
    } else {
        for (let i = start; i < arr.length; i++) {
            //将start与i作交换
            swap(arr, start, i);
            permutation(arr, start + 1);
            //交换完之後要再换回来才会是原本的字串ABC
            swap(arr, start, i);
        }
    }
};

const swap = (arr, n1, n2) => {
    [arr[n1], arr[n2]] = [arr[n2], arr[n1]];
};

permutation(["A", "B", "C"], 0);
console.log("result", result);

执行结果如下