首页 > 试题广场 >

数字和为sum的方法数

[编程题]数字和为sum的方法数
  • 热度指数：24104 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。

输入描述:
输入为两行:
 第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000)
 第二行为n个正整数A[i](32位整数)，以空格隔开。


输出描述:
输出所求的方案数
示例1

输入

5 15 5 5 10 2 3

输出

4
算法知识视频讲解
开通博客
头像 许澄
发表于 2025-02-19 14:45:40
#include <iostream> #include <vector> using namespace std; int main() { int n, sum; cin >> n >> sum; vector<in 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 muniao94
发表于 2021-09-11 17:00:16
这个题目让我感受到了算法的魅力。写的第一个解法跑一个n = 684的用例，需要100个小时才能出结果；当放弃第一个解法另换思路后，第二个解法就可以满足题目要求，1秒内出结果。下面给出两种解法，但是只介绍第二种解法思想。首先将n个数划分成两部分（代码中后缀用Left和Right表示），分别在这两部分中 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 bandiaoz
发表于 2024-12-26 16:20:15
解题思路 这是一道动态规划题目，主要思路如下： 问题分析： 给定 个正整数和目标和 从数组中选择若干数字求和 不同位置的相同数字视为不同方案 求所有可能的方案数 解决方案： 使用动态规划 表示和为 的方案数 对每个数字，更新所有可能的和 从大到小更新避免重复计算 实现细节 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客541017438号
发表于 2024-09-27 22:41:46
import sys inputs = [] for line in sys.stdin: inputs.extend(list(map(int, line.split()))) def count_combinations(n, sum, nums): dp = [[0 for 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 一场困在这里的雨
发表于 2023-08-30 11:03:48
#include <iostream> using namespace std; const int MAXN = 1e3+5; #define ll long long int a[MAXN],n,sum; ll dp[MAXN][MAXN]; //dp[i][j]: 前i个数组成j的 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Glitterosu
发表于 2022-01-17 18:04:11
dp问题 转移方程：sumcount(nums,n,targetsum)=sumcount(nums,n-1, targetsum-nums[n])+sumcount(nums,n-1,targetsum)       &nbs 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 滴滴 动态规划 Java工程师
上传者：小小
难度：
88条回答 33377浏览

热门推荐

通过挑战的用户

查看代码

相关试题

数字和为sum的方法数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号