回溯思路详解

回溯法，一般可以解决如下几种问题：

• 组合问题：N个数里面按一定规则找出k个数的集合

• 切割问题：一个字符串按一定规则有几种切割方式

• 子集问题：一个N个数的集合里有多少符合条件的子集

• 排列问题：N个数按一定规则全排列，有几种排列方式

• 棋盘问题：N皇后，解数独等等

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

 

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

回溯法三部曲

1 递归函数的返回值以及参数

2  回溯函数终止条件

3 单层搜索的过程

组合问题：N个数里面按一定规则找出k个数的集合

//  1. 确定解空间
let result = []
let step = []
//2. 确定参数  n遍历子元素的数量,k能遍历的深度
function backTracing(n, k, startindex){
    //  2. 确定回溯终止条件,这里是数组长度,确定是有一个解
    if (step.length === k) {
         result.push(Array.from(step))
        return
    }
    for (let i = startindex; i <= n; i++) {
        // 3. 确定处理节点
        step.push(i)
        backTracing(n, k, i + 1)
        step.pop()
    }
}



var combine = function (n, k) {
     result = []
     step = []
    backTracing(n, k, 1)
    return result
};

排列问题：N个数按一定规则全排列，有几种排列方式

//  1. 确定解空间,单层解和总解
let result = []
let step = []
let occupied = [0, 0, 0]
// 2. 确定回溯函数的参数和返回值
function backTracking( nums) {
    
    // 2. 确定递归终止条件
    if (step.length===nums.length ) {
        result.push(Array.from(step))
        return
    }
    for (let i = 0; i < nums.length; i++) {
        // 确定操作
        if (occupied[i] === 0) {
            step.push(nums[i])
            occupied[i] = 1
            backTracking(nums)
            occupied[i] = 0
            step.pop()
        }
    }
}
var permute = function (nums) {
    backTracking( nums)

    console.log(result)
    
    return result
};

子集问题：一个N个数的集合里有多少符合条件的子集 

与组合问题类似,不过在每一个节点收集答案而非在叶子节点

//  1 定义解空间
let result = []
let step = []
// 2 定义回溯函数的参数和反回值

function backTracing(startIndex, nums) {
    result.push(Array.from(step))
    // 3 定义终止条件
    if (startIndex === nums.length) {
        return
    }
    // // 4 定义操作,遍历每一个元素

    for(let i=startIndex;i<nums.length;i++){
        step.push(nums[i])
        backTracing(++i, nums)
        step.pop()
    }
}
var subsets = function (nums) {
    result = []
    step = []
    backTracing(0, nums)
    console.log(result)
};
subsets([1, 2, 3])

切割问题：一个字符串按一定规则有几种切割方式 

这个跟组合问题有何不同呢?

多了条件判断的组合问题

/**
 * @param {string} s
 * @return {string[][]}
 */
//  1 解空间
let result = []
let step = []
//2 回溯函数的参数和返回值
//split[]切割点数组,树宽度.count切割点个数,树深度
function backTracing(starIndex, s) {
    //3 终止条件
    if (starIndex == s.length) {
        result.push(Array.from(step))
        return
    }
    for (let i = starIndex; i < s.length; i++) {
        if (isPalindrome(s, starIndex, i)) {   // 是回文子串
            // 获取[startIndex,i]在s中的子串
            const str = s.substr(starIndex, i - starIndex + 1);
            step.push(str);
        } else {                                // 不是回文，跳过
            continue;
        }
        backTracing(i+1, s)
        step.pop()
    }
}
function isPalindrome(s, start, end) {
    for (let i = start, j = end; i < j; i++, j--) {
        if (s[i] != s[j]) {
            return false;
        }
    }
    return true;
}
var partition = function (s) {
    result=[]
    step=[]
    backTracing(0, s)
    return result
};

个人总结:

回溯算法不是很难,主要为两种

1. 以每个节点为结果集的类型(子集问题)
2. 以叶子节点为结果集的类型(排列问题,组合问题,切割问题)