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

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

热度指数：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]]

算法知识视频讲解

JavaScript Node

牛客760497705号

function combination( nums ,  target ) {
    // write code here
    const res = []
    const fn = (i, path) => {
        path.push(i)
        let sum = path.reduce((s, val) => s += val, 0)
        if (sum > target) {
            return
        }
        if (sum == target) {
            res.push([...path])
            return
        }
        for (let j = 0; j < nums.length; j++) {
            fn(nums[j], path)
            // 回溯
            path.pop()
        }
    }
    for (let i = 0; i < nums.length; i++) {
        fn(nums[i], [])
    }
    return res.length
}

发表于 2023-04-04 10:36:06 回复(0)