code.ashish.me

Atom feed

Recently added: 02 Count Of Subset Sum, 416 Partition Equal Subset Sum, 01 Subset Sum, 518 Coin Change 2, 983 Minimum Cost For Tickets

05 Best Sum

/**
 *
 * Ashish Patel
 * e: ashishsushilPatel@gmail.com
 * w: https://ashish.me
 *
 */

console.time('bestsum1')
var bestSum = function(candidates, target) {
  if (target === 0) return []
  if (target < 0) return null
  let shortestSum = candidates
  for (const candidate of candidates) {
    const remainder = target - candidate
    const result = bestSum(candidates, remainder)
    if (result !== null) {
      const sum = [...result, candidate]
      if (sum.length !== 0 && shortestSum.length > sum.length) {
        shortestSum = sum
      }
    }
  }
  return shortestSum
}
console.log(bestSum([10, 1, 2, 7, 6, 1, 5], 8))
console.timeEnd('bestsum1')

console.time('bestsum2')
var bestSum2 = function(candidates, target, dp = {}) {
  if (target in dp) return dp[target]
  if (target === 0) return []
  if (target < 0) return null
  let shortestSum = candidates
  for (const candidate of candidates) {
    const remainder = target - candidate
    const result = bestSum2(candidates, remainder, dp)
    if (result !== null) {
      const sum = [...result, candidate]
      if (sum.length !== 0 && shortestSum.length > sum.length) {
        shortestSum = sum
      }
    }
  }
  dp[target] = shortestSum
  return shortestSum
}
console.log(bestSum2([10, 1, 2, 7, 6, 1, 5], 8))
console.timeEnd('bestsum2')

Created 2021-10-14T15:18:58+01:00, updated 2021-10-15T00:34:06+01:00 · History · Edit