The subset Sum problem is stated simply, given a list of integers and a target sum, find all subsets of list that sum to the target.
I've written an application in nodejs that is able to do so for duplicates, nehative numbers, and zero. However I would like to refactor the code in less lines. I think a key step to do that is fixing the logic of the 2 loops. Currently it works but I am using labels to break and continue the logic. Is there a way of constructing the following while-ifs to remove the labels?
I feel I'm making a simple mistake in both while-ifs.
function reduceStack() {
sortStack: while (stack.length !== 0) {
let p = convertToObject(outOf(stack))
// DEAD BRANCH
if (p.problemSet.length === 0 && p.targetSum !== p.solutionSum) {
into(trash, convertToString(p))
continue sortStack
}
// ZERO SUM SUBSTITUTIONS: Solution achieved but zero sum combinations may be added. Can be commented out.
if (p.problemSet.length !== 0 && p.targetSum === p.solutionSum) {
into(answers, convertToString(p))
p.solutionSum = null
p.targetSum = 0
into(stack, convertToString(p))
continue sortStack
}
// SOLUTION FOUND
if (p.problemSet.length === 0 && p.targetSum === p.solutionSum) {
into(answers, convertToString(p))
continue sortStack
}
// WORK
if (p.problemSet.length !== 0 && p.targetSum !== p.solutionSum) {
considerN: while (p.problemSet.length !== 0) {
let actualNumber = p.problemSet[p.problemSet.length - 1]
let n = noDecimals(actualNumber)
let oppositeSign = n < 0 ? p.positiveSum : p.negativeSum
let sameSign = n < 0 ? p.negativeSum : p.positiveSum
// TOO BIG
// The Number is Too BIg and is will continue to be so along this branch.
// It is therefore removed from the array of possible integers.
if (absolute(n) > absolute(p.currentNeed - oppositeSign) && n !== p.currentNeed) {
n < 0 ? p.negativeSum = p.negativeSum - n : p.positiveSum = p.positiveSum - n
outOf(p.problemSet)
continue considerN
}
// TOO SMALL
// The number is Too Small but may be utilized later in branch.
// Therefore it is skipped on current recursive step.
if (sameSign < p.currentNeed && n !== p.currentNeed) {
break considerN
}
// PASSES TEST
// The Number is selected as a node in branch.
// Another packet containing this number is created and put into stack.
// The steps are reverse and the loop continues to discover any other posible nodes at this junction
into(p.solutionSet, actualNumber)
n < 0 ? p.negativeSum = p.negativeSum - n : p.positiveSum = p.positiveSum - n
p.solutionSum = p.solutionSum + n
p.currentNeed = p.currentNeed - n
outOf(p.problemSet)
let copyPacket = convertToString(p)
// Reverse Construction of Duplicate packet
outOf(p.solutionSet)
p.solutionSum = p.solutionSum - n
p.currentNeed = p.currentNeed + n
// Send new packet to Stack and grab next "n"
into(stack, copyPacket)
continue considerN
}
}
}
}
The complete code and link to Medium article can be found at https://github.com/ClintMulligan/subset-sum-finder
Aucun commentaire:
Enregistrer un commentaire