加起来和为目标值的组合(四)

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

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

给定一个由不同整数构成的数组 nums 和一个整数 target ，请你从 nums 找出总和是 target 的组合的个数。解集中可以重复使用 nums 中的元素。且解集中数字顺序不同视为不同的组合。

数据范围：数组长度满足 $1 \le n \le 200 \$ ，数组中的数满足 $1 \le val \le 1000 \$ , $1 \le target \le 1000 \$

示例1

输入

[1,2,3],4

输出

说明

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

示例2

输入

[9],10

输出

示例3

输入

[9],18

输出

说明

[[9,9]]

算法知识视频讲解

Python3

liangzhengjie

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

    def traverse(self, nums, now_sum, target, tmp_arr, res_s):
        if now_sum == target:
            res_s.add(tuple(tmp_arr))
            return
        
        if now_sum > target:
            return

        for i in range(len(nums)):
            tmp_arr.append(nums[i])
            self.traverse(nums, now_sum + nums[i], target, tmp_arr, res_s)
            tmp_arr.pop()

发表于 2024-04-28 21:12:23 回复(0)