程序笔记   发布时间:2022-07-21  发布网站:大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

这是一道 回溯算法的题目。按照回溯算法模板,我们需要知道

  • 选择列表---不变。
  • 路径----track
  • 结束条件---track的值等于target

模板

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,请注明来意。