回溯算法

集合

思考

回溯法三部曲
递归函数的返回值以及参数
回溯函数终止条件
单层搜索的过程

方法一

function combine(n: number, k: number): number[][] {
    let path = [],result = []
    function backTraking(n,k,startIndex){
        if(path.length===k){  // 终止条件
            result.push([...path])
            return 
        }
        for(let i=startIndex;i<=n;i++){
            path.push(i)
            backTraking(n,k,i+1)
            path.pop()  // 回溯
        }
    }
    backTraking(n,k,1)
    return result
};

组合总合 III

题号216. 组合总和 III

思考

先不需要剪枝，通过上一题来理解
长度剪枝，n剪枝

方法一无剪枝

function combinationSum3(k: number, n: number): number[][] {
    let tmpArr=[],result = []
    function backTracking(k,n,startIndex,sum){
        if(sum===n&&tmpArr.length===k){
            result.push([...tmpArr])
            return
        }
        for(let i=startIndex;i<10;i++){
            tmpArr.push(i)
            sum +=i
            backTracking(k,n,i+1,sum)
            sum -=i
            tmpArr.pop()
        }
    }
    backTracking(k,n,1,0)
    return result 
};

方法二剪枝

function combinationSum3(k: number, n: number): number[][] {
    let tmpArr=[],result = []
    function backTracking(k,n,startIndex,sum){
        if(sum===n&&tmpArr.length===k){
            result.push([...tmpArr])
            return
        }
        for(let i=startIndex;i<=tmpArr.length-k+1+9;i++){ //剪枝
            tmpArr.push(i)
            sum +=i
            if(sum<=n)backTracking(k,n,i+1,sum)  // 剪枝
            sum -=i  // 回溯
            tmpArr.pop() 
        }
    }
    backTracking(k,n,1,0)
    return result 
};

电话号码的字母组合

题号17. 电话号码的字母组合

思考

先用一个哈希表来控制映射
回溯

方法一

function letterCombinations(digits: string): string[] {
    let key = {
        2:['a','b','c'],
        3:['d','e','f'],
        4:['g','h','i'],
        5:['j','k','l'],
        6:['m','n','o'],
        7:['p','q','r','s'],
        8:['t','u','v'],
        9:['w','x','y','z']
    }
    let result = [],tmpArr =[]
    function backTracking(digits,index){
        if(!digits)return []
        if(tmpArr.length===digits.length){
            result.push(tmpArr.join(''))
            return
        }
        for(let i=0;i<key[digits[index]].length;i++){
            tmpArr.push(key[digits[index]][i])
            backTracking(digits,index+1)
            tmpArr.pop()
        }
    }
    backTracking(digits,0)
    return result
};

组合总和

题号39. 组合总和

思考

这道题由于可以重复所以递归时候startIndex不需要+1
回溯三部曲
剪枝可以利用排序之后如果前面的已经大于target了就返回

方法一没有剪枝

function combinationSum(candidates: number[], target: number): number[][] {
    let result= [],tmpArr = []
    function backTracking(sumtarget,sum,startIndex){
        if(sum===target){
            result.push(tmpArr.slice())
            return 
        }
        for(let i=startIndex;i<candidates.length;i++){
            sum+=candidates[i]
            tmpArr.push(candidates[i])
            if(sum<=sumtarget)backTracking(sumtarget,sum,i)
            tmpArr.pop()
            sum-=candidates[i]
        }
    }
    backTracking(target,0,0)
    return result
};

方法二剪枝

function combinationSum(candidates: number[], target: number): number[][] {
    candidates.sort((a,b)=>a-b)
    let result= [],tmpArr = []
    function backTracking(sumtarget,sum,startIndex){
        if(sum===target){
            result.push(tmpArr.slice())
            return 
        }
        for(let i=startIndex;i<candidates.length;i++){
            if(sum>target)return
            sum+=candidates[i]
            tmpArr.push(candidates[i])
            if(sum<=sumtarget)backTracking(sumtarget,sum,i)
            tmpArr.pop()
            sum-=candidates[i]
        }
    }
    backTracking(target,0,0)
    return result
};

组合总和 II

题号40. 组合总和 II

思考

这道题目难点在于去除，有使用标记和不使用标记两种方法
要理解这里的去重是在同一层级去重，而不是在递归里去重（这也是不使用标记这种方法使用的是i>startIndex的原理，i大于startIndex不就意味着在同一层级了吗
然后就是使用used做标记

方法一不使用used标记

function combinationSum2(candidates: number[], target: number): number[][] {
    candidates.sort((a,b)=>a-b)
    let result = [],tmpArr = []
    function backTracking(target,startIndex,sum,){
        if(sum===target){
            result.push(tmpArr.slice())
            return
        }
        for(let i=startIndex;i<candidates.length;i++){
            if(candidates[i]===candidates[i-1]&&i>startIndex){
                //若当前元素和前一个元素相等
                //则本次循环结束，防止出现重复组合
                continue
                }
            sum+=candidates[i]
            tmpArr.push(candidates[i])
            if(sum<=target)backTracking(target,i+1,sum, )
            tmpArr.pop()
            sum-=candidates[i]

        }
    }
    backTracking(target,0,0)

    return result
};

方法二使用used

function combinationSum2(candidates: number[], target: number): number[][] {
    candidates.sort((a,b)=>a-b)
    let result = [],tmpArr = []
    let used = new Array(candidates.length).fill(false);
    function backTracking(target,startIndex,sum,used){
        if(sum===target){
            result.push(tmpArr.slice())
            return
        }
        for(let i=startIndex;i<candidates.length;i++){
            if(candidates[i]===candidates[i-1]&&used[i-1]===false){
                //若当前元素和前一个元素相等
                //则本次循环结束，防止出现重复组合
                continue
                }
            used[i] = true  // used的原理在于，我们递归的时候用到的元素都是true
            sum+=candidates[i]
            tmpArr.push(candidates[i])
            if(sum<=target)backTracking(target,i+1,sum,used)
            tmpArr.pop()  
            sum-=candidates[i]
            used[i] = false  // 回溯过后就是false，而我们要去的重是树层里的

        }
    }
    backTracking(target,0,0,used)

    return result
};

分割回文串

题号131. 分割回文串

思考

判断回文串的任务就使用双指针的方法写一个简单的函数
抽象一下，其实每一个区间就是像我们之前做的集合一样
切割线就是startIndex

方法一

function partition(s: string): string[][] {
    let result = [],tmpArr = []
    function backTracking(startIndex){
        if(startIndex>=s.length){
            result.push(tmpArr.slice())
            return
        }
        for(let i=startIndex;i<s.length;i++){
           if(!isPartition(s,startIndex,i))continue
           tmpArr.push(s.slice(startIndex,i+1))
           backTracking(i+1)
           tmpArr.pop()
        }
    }
    backTracking(0)
    return result
};

function isPartition(s,l,r){
    for(let i=l,j=r;i<j;i++,j--){
        if(s[i]!==s[j])return false
    }
    return true
}

复原IP地址

题号93. 复原 IP 地址

思考

这道题目和之前那道判断回文有很大的相关，其实可以理解成回文的升级版本，都是切割字符串

思路

用tmpArr来存被分开的每个数组
回溯三部

方法一

function isValidIpSegment(str: string): boolean {  // 判断有效性
    let tempVal: number = Number(str);
    if (
        str.length === 0 || isNaN(tempVal) ||
        tempVal > 255 || tempVal < 0 ||
        (str.length > 1 && str[0] === '0')
    ) {
        return false;
    }
    return true;
}
function restoreIpAddresses(s: string): string[] {
    const result = [],tmpArr = []
    backTracking(0);
    return result;
    function backTracking(startIndex: number): void {
        if (tmpArr.length === 4 && startIndex >= s.length) {
            result.push(tmpArr.join('.'));
            return;
        }
        if (tmpArr.length === 4 || startIndex >= s.length) return;
        let tempStr: string = '';
        // i <= Math.min(s.length, startIndex + 3) 是指最大只能截取三个长度
        for (let i = startIndex + 1; i <= Math.min(s.length, startIndex + 3); i++) {
            tempStr = s.slice(startIndex, i);
            if (isValidIpSegment(tempStr)) {
                tmpArr.push(tempStr);
                backTracking(i);
                tmpArr.pop();
            }
        }
    }
};

子集

题号78. 子集

思考

回溯三部曲
函数设定
终止条件就是都遍历完成
单层

方法一

function subsets(nums: number[]): number[][] {
    let result = [],tmpArr = []
    function backTracking(startIndex){
        if(startIndex<=nums.length){
            result.push(tmpArr.slice())
        }

        for(let i=startIndex;i<nums.length;i++){
            tmpArr.push(nums[i])
            backTracking(i+1)
            tmpArr.pop()
        }
    }
    backTracking(0)
    return result
};

子集II

题号

思考

和之前的组合总合一样在树层的时候去重，可以用used和不用used两种方法

方法一不用used

function subsetsWithDup(nums: number[]): number[][] {
    nums.sort((a,b)=>a-b)
    let result = [],tmpArr = []
    function backTracking(startIndex){
        if(startIndex<=nums.length){
            result.push(tmpArr.slice())
        }

        for(let i=startIndex;i<nums.length;i++){
            // 原理和组合总和一样，树层的时候去重，树层可以理解为进行for循环而不是递归
            if(nums[i]===nums[i-1]&&i>startIndex)continue  
            tmpArr.push(nums[i])
            backTracking(i+1)
            tmpArr.pop()
        }
    }
    backTracking(0)
    return result
};

递增子序列

题号491. 递增子序列

思考

这道题目由于不能排序所以不能用上面那个没标记法的方式来做
用Set来做去重

function findSubsequences(nums: number[]): number[][] {
    let result = [],tmpArr = []
    function backTracking(startIndex){
        if(tmpArr.length>=2){
            result.push(tmpArr.slice())
        }
        let used = new Set()
        for(let i=startIndex;i<nums.length;i++){
            if((tmpArr.length===0||nums[i]>=tmpArr[tmpArr.length-1])&&!used.has(nums[i])){
                tmpArr.push(nums[i])
                used.add(nums[i])
                backTracking(i+1)
                tmpArr.pop()
            }
        }
    }
    backTracking(0)
    return result
};

全排列

题号46. 全排列

思考

现在的问题是排列问题，不在需要startIndex来去除用过的项了
那我们可以利用哈希表来控制是否用过这个项，如果用过的话就不添加了
也可以用数组来做

方法一 Set

function permute(nums: number[]): number[][] {
    let result = [],tmpArr = []
    let used = new Set()
    
    function backTracking(){
        if(tmpArr.length===nums.length){
            result.push(tmpArr.slice())
        }
        for(let i=0;i<nums.length;i++){
            if(!used.has(nums[i])){
                tmpArr.push(nums[i])
                used.add(nums[i])
                backTracking()
                tmpArr.pop()
                used.delete(nums[i])
            }
        }

    }
    backTracking()
    return result
};

方法二数组

function permute(nums: number[]): number[][] {
    let result = [],tmpArr = []
    let used = new Array(nums.length).fill(false)
    
    function backTracking(){
        if(tmpArr.length===nums.length){
            result.push(tmpArr.slice())
        }
        for(let i=0;i<nums.length;i++){
            if(!used[i]){
                tmpArr.push(nums[i])
                used[i]=true
                backTracking()
                tmpArr.pop()
                used[i]=false
            }
        }

    }
    backTracking()
    return result
};

全排列II

题号47. 全排列 II

思考

这道题和上一道题目的差别在于现在的元素中是有重复的数字了
还是用used表，然后利用我们之前在组合总和II那里学到的去重完成就可以了

方法一

function permuteUnique(nums: number[]): number[][] {
    nums.sort((a, b) => {
        return a - b
    })

    let result = []
    let path = []
    let used = new Array(nums.length).fill(false)

    function backtracing() {
        if (path.length === nums.length) {
            result.push([...path])
            return
        }
        for (let i = 0; i < nums.length; i++) {
          // 下面!used[i - 1]保证了是在树层上去重和以前的i>startIndex有异曲同工之妙
            if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
                continue
            }
            if (!used[i]) {
                used[i] = true
                path.push(nums[i])
                backtracing()
                path.pop()
                used[i] = false
            }


        }
    }
    backtracing()
    return result
};

N皇后

题号51. N 皇后

思考

N皇后的问题在于以前我们都是一维数组中做回溯，这次是二维了

方法一

function solveNQueens(n: number): string[][] {
    const board = new Array(n).fill(0).map(_=>new Array(n).fill('.'))  // 提前设置好棋盘
    const result = []
    function backTracking(n,row,board){
        if(row===n){  // 到最后的叶节点终止收集
            result.push(transformBoard(board))
            return
        }
        for(let i=0;i<n;i++){
            if(isVailid(i,row,board)===true){  // 验证 在当前列中是否有效
                board[row][i]='Q'
                backTracking(n,row+1,board)
                board[row][i]='.'
            }
        }
    }
    backTracking(n,0,board)
    return result
};

function isVailid(col,row,board){   // 判断是否合法
    const n = board.length
    if(col<0||col>=n||row<0||row>=n)return false  // 如果行列大于棋盘本身了就返回false
    // 检查列
    for(let row of board){
        if(row[col]==='Q')return false
    }
    // 检查45度方向
    let x = col,y = row
    while(y>=0&&x<n){
        if(board[y--][x++]==='Q')return false
    }
    // 检查135度方向
    x = col,y = row
    while(x>=0&&y>=0){
        if(board[y--][x--]==='Q')return false
    }
    return true
}

function transformBoard(board){
    const result = []
    for(let row of board){
        result.push(row.join(''))
    }
    return result
}

解数独

题号37. 解数独

思考

相比于N皇后只判断放置的位置，解数独还需要考虑放置的内容
所以多了两个for循环，需要用到三个for循环

方法一

/**
 Do not return anything, modify board in-place instead.
 */
function isValid(col: number, row: number, val: string, board: string[][]): boolean {
    let n: number = board.length;
    // 列向检查
    for (let rowIndex = 0; rowIndex < n; rowIndex++) {
        if (board[rowIndex][col] === val) return false;
    }
    // 横向检查
    for (let colIndex = 0; colIndex < n; colIndex++) {
        if (board[row][colIndex] === val) return false;
    }
    // 九宫格检查
    const startX = Math.floor(col / 3) * 3;
    const startY = Math.floor(row / 3) * 3;
    for (let rowIndex = startY; rowIndex < startY + 3; rowIndex++) {
        for (let colIndex = startX; colIndex < startX + 3; colIndex++) {
            if (board[rowIndex][colIndex] === val) return false;
        }
    }
    return true;
}
function solveSudoku(board: string[][]): void {
    let n: number = 9;
    backTracking(n, board);
    function backTracking(n: number, board: string[][]): boolean {
        for (let row = 0; row < n; row++) {
            for (let col = 0; col < n; col++) {
                if (board[row][col] === '.') {
                    for (let i = 1; i <= n; i++) {
                        if (isValid(col, row, String(i), board)) {
                            board[row][col] = String(i);
                            if (backTracking(n, board) === true) return true;
                            board[row][col] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
};

回溯算法

集合​

方法一​

组合总合 III​

方法一 无剪枝​

方法二 剪枝​

电话号码的字母组合​

方法一​

组合总和​

方法一 没有剪枝​

方法二 剪枝​

组合总和 II​

方法一 不使用used标记​

方法二 使用used​

分割回文串​

方法一​

复原IP地址​

方法一​

子集​

方法一​

子集II​

方法一 不用used​

递增子序列​

全排列​

方法一 Set​

方法二 数组​

全排列II​

方法一​

N皇后​

方法一​

解数独​

方法一​

集合

方法一

组合总合 III

方法一无剪枝

方法二剪枝

电话号码的字母组合

方法一

组合总和

方法一没有剪枝

方法二剪枝

组合总和 II

方法一不使用used标记

方法二使用used

分割回文串

方法一

复原IP地址

方法一

子集

方法一

子集II

方法一不用used

递增子序列

全排列

方法一 Set

方法二数组

全排列II

方法一

N皇后

方法一

解数独

方法一