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

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

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

一公升的眼泪

function combination( nums ,  target ) {
    let res = 0;
    let path = [];
    nums.sort();
    backTracking(nums, target, 0);
    return res;
    
    function backTracking(nums, target, sum){
        if(sum === target){
            res++;
            return;
        }
        if(sum > target){
            return;
        }
        for(let i = 0; i < nums.length; i++){
            sum += nums[i];
            path.push(nums[i]);
            backTracking(nums, target, sum);
            sum -= nums[i];
            path.pop();
        }
    }
}

发表于 2022-07-16 22:13:13 回复(0)