README
¶
39. Combination Sum
Description
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]
思路
DFS 深度优先搜索
循环 candidates，计算每一个数还差多少到 target，差的数作为新的 target 重复执行，直到剩下到数等于 0。
回溯
回溯算法框架。解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
- 路径：也就是已经做出的选择。
- 选择列表：也就是你当前可以做的选择。
- 结束条件：也就是到达决策树底层，无法再做选择的条件。
代码方面，回溯算法的框架：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
Documentation
¶
Overview ¶
* @lc app=leetcode id=39 lang=golang * * [39] Combination Sum * * https://leetcode.com/problems/combination-sum/description/ * * algorithms * Medium (53.12%) * Likes: 3110 * Dislikes: 97 * Total Accepted: 476K * Total Submissions: 887.9K * Testcase Example: '[2,3,6,7]\n7' * * 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. * * Note: * * * All numbers (including target) will be positive integers. * The solution set must not contain duplicate combinations. * * * Example 1: * * * Input: candidates = [2,3,6,7], target = 7, * A solution set is: * [ * [7], * [2,2,3] * ] * * * Example 2: * * * Input: candidates = [2,3,5], target = 8, * A solution set is: * [ * [2,2,2,2], * [2,3,3], * [3,5] * ] * *
Source Files