加起来和为目标值的组合

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

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

输出

[]

算法知识视频讲解

Javascript

一公升的眼泪

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

发表于 2022-07-16 21:34:37 回复(0)