回溯算法

1. 组合

77

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。

图中可以发现n相当于树的宽度，k相当于树的深度。

剪枝优化：

接下来看一下优化过程如下：

已经选择的元素个数：path.size();

还需要的元素个数为: k - path.size();

在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

1
for (int i = startIndex; i <= n; i++) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */

var combine = function(n, k) {

let result = []
let path=[]
const combineHelper = (n, k, startIndex) => {
  if (path.length === k) {
    result.push([...path]) //这里拷贝一下
    return
  }
  for (let i = startIndex; i <= n; ++i) { //这里进行剪枝操作 i <= n - (k - path.length) + 1
    path.push(i)
    combineHelper(n, k, i + 1)
    path.pop() // 回溯
  }
}
combineHelper(n, k, 1)
return result
};

2. 组合总和|||

216

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

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。

相对于77. 组合，无非就是多了一个限制，本题是要找到和为n的k个数的组合，而整个集合已经是固定的了[1,…,9]。

想到这一点了，做过77. 组合之后，本题是简单一些了。

本题k相当于树的深度，9（因为整个集合就是9个数）就是树的宽度。

例如 k = 2，n = 4的话，就是在集合[1,2,3,4,5,6,7,8,9]中求 k（个数） = 2, n（和） = 4的组合。

image-20230307202923321

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    let targetSum=n
    let path=[]
    let res=[]
    const backTraval=(sum,startIndex)=>{
        if(sum>targetSum) return // 剪枝
        if(path.length==k){
            if(targetSum==sum){
                res.push([...path])
            }
            return
        }
        for(let i=startIndex;i<=9-(k-path.length)+1;i++){ // 剪枝
            sum+=i
            path.push(i)
            backTraval(sum,i+1)
            sum-=i
            path.pop()
        }
    }
    backTraval(0,1)
    return res
};