Number Of Subset Equal To Given Sum Algorithm
The Number of Subset Equal to Given Sum Algorithm is a dynamic programming-based approach that aims to find the number of subsets in a given set of integers whose sum is equal to a specified target sum. This problem is an extension of the classic subset sum problem, where the goal is to determine whether there is a subset with a sum equal to a given target. In this algorithm, the focus is not only on the existence of such a subset but also on counting the number of such subsets. This algorithm is particularly useful in combinatorics, probability, and various real-world applications such as financial portfolio management and resource allocation.
The algorithm employs a bottom-up approach by constructing a two-dimensional table, where the rows represent the individual elements of the given set, and the columns represent possible sums ranging from 0 to the target sum. The table is filled by iterating through each element of the set and computing the number of subsets that can be formed with the current element and the remaining elements to reach a particular sum. The value in the table cell represents the number of subsets using the first i elements that add up to the target sum. The final result is obtained from the last cell of the table, indicating the total number of subsets using all elements of the set that have a sum equal to the given target. This approach ensures the efficient and optimal computation of the solution while avoiding redundancy and overlapping subproblems.
/*
Given an array of non-negative integers and a value sum,
determine the total number of the subset with sum
equal to the given sum.
*/
/*
Given solution is O(n*sum) Time complexity and O(sum) Space complexity
*/
function NumberOfSubsetSum (array, sum) {
const dp = [] // create an dp array where dp[i] denote number of subset with sum equal to i
for (let i = 1; i <= sum; i++) {
dp[i] = 0
}
dp[0] = 1 // since sum equal to 0 is always possible with no element in subset
for (let i = 0; i < array.length; i++) {
for (let j = sum; j >= array[i]; j--) {
if (j - array[i] >= 0) {
dp[j] += dp[j - array[i]]
}
}
}
return dp[sum]
}
function main () {
const array = [1, 1, 2, 2, 3, 1, 1]
const sum = 4
const result = NumberOfSubsetSum(array, sum)
console.log(result)
}
main()
