加起来和为目标值的组合

[编程题]加起来和为目标值的组合

热度指数：2864 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无重复元素的正整数数组 nums 和一个正整数 target ，找出 nums 中所有可以使数字之和为目标数 target 的组合，nums 中的数可以重复选取，只要选出的组合中有一个数不同则视为是不同组合。

数据范围：数组长度满足 $1 \le len(nums) \le 30 \$ , 数组中的元素满足 $1 \le val\le 200 \$ ， $1 \le target \le 500 \$ ，保证组合数结果少于 150 个

示例1

输入

1,[1]

输出

[[1]]

示例2

输入

5,[1,4,5]

输出

[[1,4],[5],[1,1,1,1,1]]

示例3

输入

5,[2]

输出

[]

算法知识视频讲解

查看答案及解析

Python3

liangzhengjie

经典回溯解法

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param target int整型 
# @param nums int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def combinationCount(self , target: int, nums: List[int]) -> List[List[int]]:
        # write code here
        res = []
        self.traverse(nums, 0, [], res, target)
        return res

    def traverse(self, nums, now, tmp, res, target):
        if now == target:
            res.append(tmp.copy())
            return

        if now > target:
            return

        for i in range(len(nums)):
            tmp.append(nums[i])
            self.traverse(nums[i:], now + nums[i], tmp, res, target)
            tmp.pop()

编辑于 2024-04-21 15:04:25 回复(0)

Python3

牛客976294号

class Solution:
    def sub_process(self, target, nums, arr, res, start):
        total = sum(arr)
        if total == target:
            res.append(arr)
        else:
            for i in range(start, len(nums)):
                if nums[i] + total <= target:
                    self.sub_process(target, nums, arr+[nums[i]], res, i)

    def combinationCount(self , target: int, nums: List[int]) -> List[List[int]]:
        # write code here
        res = []
        self.sub_process(target, nums, [], res, 0)
        return res

发表于 2023-10-31 19:50:51 回复(0)