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

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

热度指数：1498 时间限制：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]]

算法知识视频讲解

小谷围做题家

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param target int整型 
 * @return int整型
*/
func combination( nums []int ,  target int ) int {
    ans:=0
    var dfs func(int)
    dfs=func(sum int){
        if sum>=target{
            if sum==target{
                ans++
            }
            return
        }
        for i:=0;i<len(nums);i++{
            sum+=nums[i]
            dfs(sum)
            sum-=nums[i]
        }
    }
    dfs(0)
    return ans
}

发表于 2023-03-18 20:27:53 回复(0)