/*
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()