Skip to content

Instantly share code, notes, and snippets.

@sunny-mittal
Created March 30, 2018 05:13
Show Gist options
  • Save sunny-mittal/58172fa56f3e246cd68ea52538bea764 to your computer and use it in GitHub Desktop.
Save sunny-mittal/58172fa56f3e246cd68ea52538bea764 to your computer and use it in GitHub Desktop.
function canIMake(list, target) {
if (target === 1) return true
if (target === 0) return false
if (list.length === 0) return false
if (list.length === 1) {
if (list[0] % target !== 0) return false
return true
}
const modded = list.map(val => val % target)
return calculate(modded, 1, target, [modded[0], -modded[0]])
}
function calculate(list, position, target, runningTotals) {
if (position == list.length) {
const midpoint = Math.ceil(runningTotals.length / 2)
return runningTotals.slice(0, midpoint).indexOf(0) !== -1
}
const newTotals = []
for (let i = 0; i < runningTotals.length; i++) {
const curr = runningTotals[i]
newTotals.push(curr + list[position], curr - list[position])
}
return calculate(list, position + 1, target, newTotals)
}
canIMake([1,2,3,4,6], 4) // true
canIMake([1,3,9], 2) // false
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment