Voyz's Studio.

LeetCode算法笔记--组合总和

字数统计: 253阅读时长: 1 min
2020/12/12 Share

LeetCode算法笔记–Day39

39. Combination Sum

题目:

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

example
input: candidates = [2,3,6,7], target = 7
output: [
[7],
[2,2,3]
]

Analyze:

方法一:回溯递归

fe32ae9cee9ec8e2545d038d80a8da70d809eed01c153c6f0076801baab5010d-39-1.png

My Answer:

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
29
30
31
32
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
// 先排序, 方便去重
candidates.sort();
const path = [],
ans = []
backtrack(target, path, candidates, ans)
return ans
}

// 实质上就是树的遍历, target是当前节点要达到的目标值, path是当前的路径
function backtrack(target, path, candidates, ans) {
// target < 0 这条路结束
if (target < 0) return
// target = 0 找到一个方案, 生成快照放入ans中
if (target === 0) {
ans.push([...path])
return
}
// 对每个备选节点进行回溯操作
for (let i = 0; i < candidates.length; i++) {
const val = candidates[i]
path.push(val)
// 由于排过序了, 所以备选路径只需要当前节点和之后的节点
backtrack(target - val, path, candidates.slice(i), ans)
path.pop()
}
}
CATALOG
  1. 1. LeetCode算法笔记–Day39
  2. 2. 39. Combination Sum
    1. 2.1. 题目:
    2. 2.2. Analyze:
      1. 2.2.1. 方法一:回溯递归
    3. 2.3. My Answer: