算法简记- 全排

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

var permute = function(nums) {
    let res = [];
    let track = [];
    backTrack(nums, track, res);
    return  res;
};
let backTrack = (nums, track, res) => {
    if (track.length === nums.length) {
        res.push([].concat(track));
        return;
    }
    for (let i = 0; i < nums.length; i++) {
        if (track.includes(nums[i])){
            continue;
        }
        track.push(nums[i]);
        backTrack(nums, track, res);
        track.pop();
    }
}

2、// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

var solveNQueens = function(n) {
    let res = [];
    let queueRes = Array.from(new Array(n), () => {return new Array(n).fill('.')});
    backTrack(res, 0, queueRes);
    return res;
};
let backTrack = (res, row, queueRes) => {
    let n = queueRes.length;
    if (row === n) {
        let arr = queueRes.map(item => {
            return item.join('');
        })
        res.push(arr);
        return;
    }

    for (let clo = 0; clo < n; clo++) {
        if (isValide(queueRes, row, clo)) {
            continue;
        }
        queueRes[row][clo] = 'Q';
        backTrack(res, row + 1, queueRes);
        queueRes[row][clo] = '.';

    }
}
let isValide = (queueRes, row, clo) => {
    let n = queueRes.length;
    for (let i = 0; i < n; i++) { // 列检查
        if (queueRes[i][clo] === 'Q') {
            return true;
        }
    }
    for (let i = row - 1, j = clo + 1; i >= 0 && j < n; i--, j++ ) { // 右上
        if (queueRes[i][j] === 'Q') {
            return true;
        }
    }
    for (let i = row - 1, j = clo - 1; i >= 0 && j >= 0; i--, j--) {
        if (queueRes[i][j] === 'Q') {
            return true;
        }
    }
    return false;
}

solveNQueens(4);

3、// . 串联所有单词的子串

 var findSubstring = function(s, words) {
    let res = [];
    let len = words[0].length;
    let wordNum = words.length;
    let totalLen = len * wordNum;

    for (let i = 0; i <= s.length - totalLen; i++) {
        let arr = [...words];
        let allStr = s.substring(i);
        dfs(arr, i, allStr);
    }
    function dfs(arr, start, allStr) {
        if (!arr.length) {
            res.push(start);
        }
        let str = allStr.substring(0, len);
        let index = arr.findIndex(item => item === str);
        if (index > -1) {
            arr.splice(index, 1);
            dfs(arr, start, allStr.substring(len));
        }
    }
    console.log(res)
    return res;
};

let b = "barfoothefoobarman", words = ["foo","bar"];
// let b ="wordgoodgoodgoodbestword",words = ["word","good","best","good"];
findSubstring(b,words);