首页 > 试题广场 >

加起来和为目标值的组合

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

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

输出

[]

算法知识视频讲解

C++

牛娃牛娃

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int>&nums,int target, int sum,int startindex){
        if(sum==target) {
            res.push_back(path);
            return ;
        }
        for(int i=startindex;i<nums.size()&&sum+nums[i]<=target;i++){
            sum+=nums[i];
            path.push_back(nums[i]);
            backtracking(nums,target,sum, i);
            sum-=nums[i];
            path.pop_back();
        }
    }
    vector<vector<int> > combinationCount(int target, vector<int>& nums) {
        // write code here
        res.clear();
        path.clear();
        if(nums.size()==0)return res;
        sort(nums.begin(),nums.end());
        backtracking(nums,target,0,0);
        return res;
    }
};

发表于 2022-03-17 13:36:44 回复(0)

QNBZ

class Solution {
public:
    vector<vector<int>>tmp;
     void dfs(vector<int>&nums,int start,int target,vector<int>list)
     {
         if(target==0){tmp.push_back(list);return ;}
         if(target<0)return ;
         for(int i=start;i<nums.size();i++)
         {
             list.push_back(nums[i]);
             dfs(nums,i,target-nums[i],list);
             list.pop_back();
         }
     }
    vector<vector<int> > combinationCount(int target, vector<int>& nums) {
        vector<int>list;
        dfs(nums,0,target,list);
        return tmp;
    }
};

发表于 2022-01-05 00:20:46 回复(0)

Java

pein531

经典回溯做法

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    ArrayList<ArrayList<Integer>> results = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> combinationCount (int target, int[] nums) {
        // write code here
        dfs(nums, 0, target, new ArrayList<Integer>());
        return results;
    }
    
    private void dfs(int[] nums, int depth, int rest, ArrayList<Integer> path) {
        if(rest < 0){
            return;      // 凑过头了，直接返回
        }
        if(rest == 0){
            results.add(new ArrayList<Integer>(path));     // 刚好凑到目标，返回一组结果
        }else{
            for(int i = depth; i < nums.length; i++){
                path.add(nums[i]);
                dfs(nums, i, rest - nums[i], path);
                path.remove(path.size() - 1);     // 回溯
            }
        }
    }
}

发表于 2021-12-15 09:27:08 回复(0)

Python3

liangzhengjie

经典回溯解法

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

    def traverse(self, nums, now, tmp, res, target):
        if now == target:
            res.append(tmp.copy())
            return

        if now > target:
            return

        for i in range(len(nums)):
            tmp.append(nums[i])
            self.traverse(nums[i:], now + nums[i], tmp, res, target)
            tmp.pop()

编辑于 2024-04-21 15:04:25 回复(0)

Python3

牛客976294号

class Solution:
    def sub_process(self, target, nums, arr, res, start):
        total = sum(arr)
        if total == target:
            res.append(arr)
        else:
            for i in range(start, len(nums)):
                if nums[i] + total <= target:
                    self.sub_process(target, nums, arr+[nums[i]], res, i)

    def combinationCount(self , target: int, nums: List[int]) -> List[List[int]]:
        # write code here
        res = []
        self.sub_process(target, nums, [], res, 0)
        return res

发表于 2023-10-31 19:50:51 回复(0)

小谷围做题家

package main

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

发表于 2023-03-10 01:00:12 回复(0)

布加迪.威龙

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    void dfs(vector<vector<int>>&res,int start,vector<int>&path, int target, vector<int>& nums){
        if(target==0){
            res.push_back(path);
            return ;
        }
        for(int i=start;i<nums.size();i++){
            if(nums[i]<=target){
                path.push_back(nums[i]);
                dfs(res, i, path, target-nums[i], nums);
                path.pop_back();
            }
        }
    }
    vector<vector<int> > combinationCount(int target, vector<int>& nums) {
        vector<vector<int>>res;
        vector<int>path;
        sort(nums.begin(),nums.end());
        dfs(res, 0, path,  target, nums);//2^n
        return res;
    }
};

发表于 2022-07-19 09:11:10 回复(0)

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)

C++

牛客487629784号

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > combinationCount(int target, vector<int>& nums) {
        // write code here
        help(target,nums,0);
        return rt;
    }
    void help(int res,vector<int>& nums,int idx)
    {
        if(res<0)
        {
            return;
        }
        if(res==0)
        {
            rt.push_back(tmp);
        }
        for(int i=idx;i<nums.size();i++)
        {
            tmp.push_back(nums[i]);
            help(res-nums[i],nums,i);
            tmp.pop_back();
        }
    }
private:
    vector<vector<int>> rt;
    vector<int> tmp;
};

发表于 2022-06-30 17:54:41 回复(0)

JavaScript Node

乱不能

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param target int整型
* @param nums int整型一维数组
* @return int整型二维数组
*/
let result = []
function combinationCount( target , nums ) {
// write code here
let path = []
dfs(nums,0,target,path)
return result
}
function dfs(nums,start,res,path){
if(res < 0) return
if (res == 0) {
result.push(path.slice())

}
else{
for(let i = start ; i < nums.length ; i++){
path.push(nums[i])
dfs(nums ,i ,res - nums[i] , path)
path.pop()
}
}

}
module.exports = {
combinationCount : combinationCount
};

发表于 2022-01-20 00:59:23 回复(0)