回溯算法----组合问题

1. 什么情况会用到回溯算法

我理解的就是无法用for循环遍历穷举出所有结果的问题，例如从n个数中选取m个数的组合问题，由于m无法确定，所以传统的for循环无法解决这种问题。需要用到回溯递归，也就是for循环中有递归。推荐一个算法学习网站代码随想录

2. 回溯算法解决的问题

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

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

3. 回溯算法模板

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

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

4. 回溯算法实例

4.1 组合问题

求n个数的k个数组合

var combine = function(n, k) {
    let res = []//存最终的结果集
    let path = []//存符合条件的结果
    //定义回溯算法
    function backtracking(n,k,startIndex){
        if(path.length === k){
            res.push([...path])
            return 
        }
        for(let i = startIndex;i<=n;i++){
            path.push(i)//处理节点
            backtracking(n,k,i+1)//递归
            path.pop()//回溯，撤销处理的节点
        }
    }
    backtracking(n,k,1)
    return res
};

其中path存
剪枝
当n=k=4时，从元素2开始的遍历就都没有意义，所以将递归中每一层的for循环的起始位置进行一个剪枝。

1. 已经选择的元素个数：path.size();
2. 还需要的元素个数为: k - path.size();
3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
   为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
   举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
   从2开始搜索都是合理的，可以是组合[2, 3, 4]。

var combine = function(n, k) {
    let res = []
    let path = []
    function backtracking(n,k,startIndex){
        if(path.length === k){
            res.push([...path])
            return 
        }
        for(let i = startIndex;i<=n-(k-path.length)+1;i++){//对i进行剪枝
            path.push(i)
            backtracking(n,k,i+1)
            path.pop()
        }
    }
    backtracking(n,k,1)
    return res
};

4.2 组合总和

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
来源：力扣

var combinationSum3 = function(k, n) {
    let res =[]
    let path = []
    function backTracking(startIndex,sum){
        if(sum>n) return//剪枝，当sum大于n时就不用继续了
        if(path.length === k){
            var sum = path.reduce((x,y)=> x+y)
            if( sum === n){
                res.push([...path])
            }
            return 
        }
        for(let i =startIndex;i<=9-(k-path.length)+1;i++){//剪枝同上
            path.push(i)
            backTracking(i+1)
            path.pop()
        }
    }
    backTracking(1,0)
    return res
};

4.3 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

来源：力扣（LeetCode）

var letterCombinations = function(digits) {
    const k = digits.length;
    const map = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"];
    if(!k) return []
    if(k === 1) return map[digits].split("")
    let res = []
    let path = []
    function backtracking(n,k,a){
        if(path.length === k){
            res.push(path.join(''))
            return
        }
        for(let v of map[n[a]]){//map[n[a]]取数字对应的字符集
            path.push(v)//处理
            backtracking(n,k,a+1)//递归
            path.pop()//回溯
        }
    }
    backtracking(digits,k,0)
    return res

};

如果是一个集合来求组合的话，就需要startIndex ; 如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex

4.4 组合总和(可重复)

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
来源：力扣（LeetCode）

var combinationSum = function(candidates, target) {
    let res = []
    let path = []
    candidates.sort((a,b)=>a-b)// 先进行排序
    function backtracking(j,sum){
        if(sum === target){
            res.push([...path])
            return
        }
        for(let i=j;i<candidates.length;i++){
            let n = candidates[i]
            if(n>target-sum) break//因为本题没有组合数量限制，所以只要元素总和大于target就算结束
            path.push(n)
            sum+=n
            backtracking(i,sum)// 因为无限制重复选取，所以不是i+1
            path.pop()//回溯
            sum-=n//回溯
        }
    }
    backtracking(0,0)
    return res
};

4.5 组合总和(不可重复)

var combinationSum2 = function(candidates, target) {
    let res = [],path = []
    const len = candidates.length
    candidates.sort((a,b)=>a-b)
    function backtracking(sum,i){
        if(sum === target){
            res.push([...path])
            return 
        }
        for(let j=i;j<len;j++){
            let n = candidates[j]
            if(j>i && candidates[j]===candidates[j-1]){
                //若当前元素和前一个元素相等
                //则本次循环结束，防止出现重复组合
                continue
            }
            //如果当前元素值大于目标值-总和的值
            //由于数组已排序，那么该元素之后的元素必定不满足条件
            //直接终止当前层的递归
            if(n>target-sum) break
            path.push(n)
            sum += n
            backtracking(sum,j+1)
            path.pop()
            sum -= n
        }
    }
    backtracking(0,0)
    return res

};