首页 > 试题广场 >

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

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

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

算法知识视频讲解

Java

pein531

深度优先搜索，由于数组中每个数不限制选择次数，因此每一层深度都可以选相同的数。用rest表示还剩多少数需要凑，分为以下三种情况：

当rest=0时，表示凑足了target，方案数自增；
当剩下的rest<0时，表示凑过头了，当前的组合方案无效；
当rest>0时，就尝试当前选择数组中所有数的可能性，rest-=nums[i]后继续下一层的搜索。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    int count = 0;
    public int combination (int[] nums, int target) {
        // write code here
        dfs(nums, target);
        return count;
    }
    
    private void dfs(int[] nums, int rest) {
        if(rest < 0){
            return;     // 凑过头了，本次组合无效
        }
        if(rest == 0){
            // 凑足目标值了就添加答案
            count++;
        }else{
            // 否则遍历此时选所有数的可能，继续递归选下一个数
            for(int i = 0; i < nums.length; i++){
                dfs(nums, rest - nums[i]);
            }
        }
    }
}

编辑于 2021-12-17 14:30:14 回复(0)

Python3

liangzhengjie

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

    def traverse(self, nums, now_sum, target, tmp_arr, res_s):
        if now_sum == target:
            res_s.add(tuple(tmp_arr))
            return
        
        if now_sum > target:
            return

        for i in range(len(nums)):
            tmp_arr.append(nums[i])
            self.traverse(nums, now_sum + nums[i], target, tmp_arr, res_s)
            tmp_arr.pop()

发表于 2024-04-28 21:12:23 回复(0)

C++

矜持的微笑

class Solution {
     private:
    vector<vector<int>> result;
    vector<int> path;
public:
   int combination(vector<int>& nums, int target) {
        // write code here
        result.clear();
        path.clear();
        sort(nums.begin(),nums.end());
        backtracking(nums,target,0,0);
        return result.size();
    }
    void backtracking(vector<int>& candidates,int target,int sum,int startIndex){
        if(sum==target){
           result.push_back(path);
           return;
        }
        for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,target,sum,0);
            sum-=candidates[i];
            path.pop_back();
        }
    }

};

编辑于 2024-01-28 19:04:45 回复(0)

thymea

为什么总是

调试运行出错，退出码：1

发表于 2023-09-13 09:44:17 回复(0)

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)

Java

牛客585981974号

public int combination (int[] nums, int target) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        dfs(res, list, nums, target);
        return res.size();
    }
    public void dfs(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list,
                    int[] nums, int target) {
        if(target == 0){
            res.add(new ArrayList<Integer>(list));
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > target) {
                return;
            }
            list.add(i);
            dfs(res, list, nums, target - nums[i]);
            list.remove(list.size() - 1);
        }
    }

发表于 2023-04-01 00:54:03 回复(0)

小谷围做题家

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)

C++

阿金要努力

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

发表于 2023-03-05 13:37:28 回复(0)

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)

Java

菲尼克斯弗兰克

标准的回溯框架，写一个backtrack辅助函数就可以了，重点就是终止条件、已选择、达到条件

public int combination (int[] nums, int target) {
    backTrack(nums, target);
    return cnt;
}
public int sum = 0, cnt = 0;
public void backTrack(int[] nums, int target) {
    if (sum > target) return;
    if (sum == target) {
        cnt++;
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        backTrack(nums, target);
        sum -= nums[i];
    }
}

发表于 2022-01-11 12:58:03 回复(0)

提交观点

问题信息

数组递归

难度：

10条回答 23收藏 3181浏览

通过挑战的用户

查看代码

牛客13928...

2022-11-09 23:15:15
TSLydia

2022-09-16 13:08:25
牛客11870...

2022-09-15 21:16:22
正在卷的乌龟很刻苦

2022-09-15 10:30:10
牛客21276...

2022-09-15 00:21:39

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

输入

输出

说明

输入

输出

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题