DFS与回溯法

背景

回溯法（backtrack）常用于遍历列表所有子集，是 DFS 深度搜索一种，一般用于全排列，穷尽所有可能，遍历的过程实际上是一个决策树的遍历过程。时间复杂度一般 O(N!)，它不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

模板

result = []
function backtrack(选择列表,路径):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(选择列表,路径)
        撤销选择

核心就是从选择列表里做一个选择，然后一直递归往下搜索答案，如果遇到路径不通，就返回来撤销这次选择。

练习

基础题

• subsets
• subsets-ii
• permutations
• permutations-ii

挑战题目

• combination-sum
• letter-combinations-of-a-phone-number
• word-search
• palindrome-partitioning
• restore-ip-addresses

示例

subsets

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

遍历过程

var subsets = function(nums) {
    let result = [];
    // 记录走过的路径
    let track = [];
    function backtrack( nums, start, track) {
        console.log(track,result);
        result.push([...track]);
        for (let i = start; i < nums.length; i++) {
            // 做选择
            track.push(nums[i]);
            // 回溯
            backtrack(nums, i + 1, track);
            // 撤销选择
            track.pop();
        }
    }
    backtrack(nums, 0, track);
    return result;
};

subsets-ii

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

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
let subsetsWithDup = function(nums) {
    let ans = [];
    let track = [];
    let n = nums.length;
    nums = nums.sort((a, b) => a - b);
    let dfs = function(start){
        ans.push([...track]);
        for( let i = start; i < n; i++ ) {
            if( i > start && nums[i] === nums[i-1]) continue;
            track.push(nums[i]);
            dfs(i+1);
            track.pop();
        }
    };  
    dfs(0);
    return ans;
};

permutations

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

思路：需要记录已经选择过的元素，满足条件的结果才进行返回

var permute = function(nums) {
    let result = [];
    let track = [];
    let backTrack = function(){
        if(track.length === nums.length) {
            result.push([...track]);
        }
        for(let i =0; i < nums.length; i++) {
            if(track.indexOf(nums[i]) !== -1) continue;
            track.push(nums[i]);
            backTrack();
            track.pop();
        }
    };
    backTrack()
    return result;
};

permutations-ii

给定一个可包含重复数字的序列，返回所有不重复的全排列。

var permuteUnique = function(nums) {
    if(nums.length === 0) return [];
    let n = nums.length;
    let ans = [];
    let track = [];
    let st = [];
    nums = nums.sort((a,b) => {return a - b});
    function dfs(u, start){
        if(u === n) {
            ans.push([...track]);
            return;
        }
        for(let i = start; i < n; i++) {
            if(!st[i]){
                st[i] = true;
                track[i] = nums[u];
                let s = u + 1 < n && nums[u + 1] == nums[u] ? i + 1 :0;
                dfs(u + 1, s)
                st[i] = false;
            }
        }
    };
    dfs(0,0);
    return ans;
};

letter-combinations-of-a-phone-number

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

// 第一种，大雪菜上学的
var letterCombinations = function(digits) {
    if(!digits) return [];
    let temp =['','','abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
    let state = [''];
    for ( let i of digits.split('')) {
        let track = [];
        for( let c of temp[i]) {
            for( let s of state) {
                track.push(s + c );
            }
        }
        state = track;
    }
    return state
};
// 第二种回溯 
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    if(!digits) return [];
    let digitsList = digits.split('');
    let temp =['','','abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
    let result = [];
    let track = [];
    var dfs = function(start){
        if(start > digitsList.length) return;
        if(track.length === digitsList.length) {
            result.push(track.join(''));
            return;
        }
        let index = digitsList[start];
        let list = temp[index].split('');
        for(let i = 0; i < list.length; i++){
            track.push(list[i]);
            console.log(track);
            dfs(start + 1);
            track.pop();
        }
    };
    dfs(0);
    return result
};

word-search

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
let m, n;
let dx = [-1, 0, 1, 0];
let dy = [0, 1, 0, -1];
var exist = function(board, word) {
    if(board.length === 0 || board[0].length == 0) return false;
    m = board.length, n = board[0].length;
    for(let i = 0; i < m; i++ ) {
        for( let j = 0; j < n; j++) {
            if(dfs(board, word,i, j , 0)){
                return true;
            }
        }
    }
    return false;
};
var dfs =  function (board, word, x, y, u) {
    if(board[x][y] != word[u]) return false;
    if(u == word.length - 1) return true;
    board[x][y] = '.';
    for(let i = 0; i < 4; i++) {
        let a = x + dx[i], b = y + dy[i];
        if(a >= 0 && a < m && b >= 0 && b < n) {
            if(dfs(board, word, a, b , u + 1)) {
                return true;
            }
        }
    }
    board[x][y] = word[u];
    return false
}

[x] combination-sum

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    if(candidates.length === 0) return [];
    let result = [];
    // 记录走过的路径
    let track = [];
    function backtrack( start,leave) {
        if(leave === 0 ){
            result.push([...track]);
            return
        }
        for (let i = start; i < candidates.length; i++) {
            // 做选择
            if(leave - candidates[i] >= 0 ) {
                track.push(candidates[i]);
                 // 回溯
                backtrack(i, leave - candidates[i] );
                // 撤销选择
                track.pop();
            }
        }
    }
    backtrack(0, target);
    return result;
};