英文:
Subset finder for different set lengths
问题
问题：您需要编写一个算法，找到给定整数数组中的子数组数量，其总和等于目标数字。编写一个函数来计算总和等于目标数字的子数组的数量。
示例：
输入：
数组：[1, 2, 3, 4, 5, 6]
目标总和：8
输出：
子数组的数量：4（[6, 2]，[5, 3]，[5, 2, 1]，[4, 3, 1]）
注意：您可以使用任何编程语言来解决这个问题。
注意：该函数应适用于不同的集合长度。
英文:
Question: You need to write an algorithm that finds the number of subarrays in a given integer array whose sum is equal to a target number. Write a function that calculates the count of subarrays whose sum equals the target number.
Example:
Input:
Array: [1, 2, 3, 4, 5,6]
Target Sum: 8
Output:
Count of Subarrays:4 ([6,2],[5,3],[5,2,1],[4,3,1])
note: you can solve it in any programming language you want
note: the function should be suitable for different set lengths
答案1
得分: 0
动态规划方法：
创建大小为 Sum+1 的数组/列表 A[]。
将其填充为零，除了 A[0]=1（表示制作空子集的一种方式）。
对于数组中的每个值 V：
对于从 Sum 到 V 的每个索引 i：
A[i] += A[i-V]
打印 A[Sum]
发生了什么：
数组 A[] 存储了所有可能和的子集数量（您可以在外部循环的每轮之后检查其内容）。
我们可以使用项目 V 和总和为 i-V 的任何子集来生成总和 i。
反向扫描 - 以避免对相同项目进行重复计数。
英文:
Dynamic programming approach:
Make array/list A[] of size Sum+1
Fill it with zeros, except for A[0]=1 (there is one way to make empty subset)
for every value V from array:
for every index i from Sum downto V:
A[i] += A[i-V]
print A[Sum]
What's happen:
Array A[] holds number of subsets for all possible sums (you can inspect it's contents after every round of outer loop).
We can make sum i using item V and any subsets with sum i-V.
Reverse scan - to avoid double counting of the same item.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论