大佬教程收集整理的这篇文章主要介绍了39.组合总和【测试岗常见算法题】,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
39.组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。 解集不能包含重复的组合。 示例 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] ]
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/combination-sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这是一道 回溯算法的题目。按照回溯算法模板,我们需要知道
result = [];
void BACktrack(路径, 选择列表){
if(满足结束条件){
result.add(路径);
return;
}else{
for 选择 in 选择列表{
//做选择
路径.add(选择);
选择列表.remove(选择);(看选择列表是不是要跟着变化)
BACktrack(路径, 选择列表);
//去除选择
路径.removeLast();
选择列表.add(选择);(看选择列表是不是要跟着变化)
}
}
}
import copy
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.ret = []
self.BACktrack([], candidates, target)
return self.ret
def BACktrack(self, tarck, candidates, target):
if target == 0:
temp = copy.deepcopy(tarck)
temp.sort()
if temp not in self.ret:
self.ret.append(temp)
elif target<0:
return
else:
for i in candidates:
tarck.append(i)
self.BACktrack(tarck, candidates, target-i)
tarck.pop()
以上是大佬教程为你收集整理的39.组合总和【测试岗常见算法题】全部内容,希望文章能够帮你解决39.组合总和【测试岗常见算法题】所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。