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