class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
}
};
剑指 Offer II 081. 允许重复选择元素的组合
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
示例 1：
输入: candidates =[2,3,6,7],target =7输出: [[7],[2,2,3]]
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
示例 4：
输入: candidates =[1],target =1输出: [[1]]
示例 5：
输入: candidates =[1],target =2输出: [[1,1]]
提示：
1 <= candidates.length <= 301 <= candidates[i] <= 200candidate 中的每个元素都是独一无二的。1 <= target <= 500
注意：本题与主站 39 题相同： https://leetcode.cn/problems/combination-sum/
原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2.6 MB, 提交时间: 2022-11-10 20:22:17
func combinationSum(candidates []int, target int) (ans [][]int) {
comb := []int{}
var dfs func(target, idx int)
dfs = func(target, idx int) {
if idx == len(candidates) {
return
}
if target == 0 {
ans = append(ans, append([]int(nil), comb...))
return
}
// 直接跳过
dfs(target, idx+1)
// 选择当前数
if target-candidates[idx] >= 0 {
comb = append(comb, candidates[idx])
dfs(target-candidates[idx], idx)
comb = comb[:len(comb)-1]
}
}
dfs(target, 0)
return
}
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2022-11-10 20:20:54
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
n = len(candidates)
res = []
def backtrack(i, tmp_sum, tmp):
if tmp_sum > target or i == n:
return
if tmp_sum == target:
res.append(tmp)
return
for j in range(i, n):
if tmp_sum + candidates[j] > target:
break
backtrack(j, tmp_sum + candidates[j], tmp + [candidates[j]])
backtrack(0, 0, [])
return res