GeezerVison is showing github.com — JavaScript/Backtracking/SumOfSubset.js at master · Randomlyclueless/JavaScript

Expand file tree

SumOfSubset.js

Copy path

More file actions

Latest commit

History

64 lines (54 loc) · 2.09 KB

SumOfSubset.js

Copy path

File metadata and controls

64 lines (54 loc) · 2.09 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

* Sum of Subset problem

* Given an ordered set W of non-negative integers and a value K,

* determine all possible subsets from the given set W whose sum

* of its elements equals to the given value K.

* More info: https://www.geeksforgeeks.org/subset-sum-backtracking-4/

* @param {number[]} set Original set of numbers

* @param {number[]} subset Subset being evaluated

* @param {number} setIndex Index from set of last element in subset

* @param {number} Sum of elements from subset

* @param {targetSum} The target sum on which the subset sum is compared to

* @returns {number[][]} Subsets whose elements add up to targetSum

const sumOfSubset = (set, subset, setindex, sum, targetSum) => {

// Base case where the subset sum is equal to target sum

// Evaluation of following subsets on this path will always add up to

// greater than targetSum, so no need to continue

if (sum === targetSum) return [subset]

// This and following subsets on this path will always add up to

// greater than targetSum, so no need to continue

if (sum > targetSum) return []

// Initialize results array. Will contain only valid subsets

let results = []

// Slice gets from the set all the elements at the right of the last element

// to be evaluated (last element of subset)

// forEach iterated on the resulting array

set.slice(setindex).forEach((num, index) => {

// The next subset to be evaluated, current subset plus next element

const nextSubset = [...subset, num]

// Next index from the set. Current set index plus iteration index

// index starts at 0, so a + 1 is required

const nextSetIndex = setindex + index + 1

// Sum of elements from the next subset to be evaluated

const nextSum = sum + num

// Call recursively the sumOfSubset for the nextSubset

const subsetResult = sumOfSubset(

set,

nextSubset,

nextSetIndex,

nextSum,

targetSum

)

// Concat the recursive result with current result array

results = [...results, ...subsetResult]

})

// Return results

return results

}

export { sumOfSubset }