/subsetsum

JavaScript solution for subset sum problem

Primary LanguageJavaScriptMIT LicenseMIT

The Problem

Given an array of numbers arr and a number S, find 4 different numbers in arr that sum up to S.

Write a function that gets arr and S and returns an array with 4 indices of such numbers in arr, or null if no such combination exists. Explain and code the most efficient solution possible, and analyze its runtime and space complexity.

Hints:

  • Any solution of more than O(n^2) is not efficient enough. Please rate your peer feedback accordingly.
  • The array is not sorted, and may hold any real number (positive, negative, zero, integer or fraction)

For Example:

const a = [17, 2, 8, 34, 4, 0.5, 42, 6, 3, 7, 15, 14, 9]
S = 20

Solution should return:

2 + 8 + 4 + 6 = 20
3 + 7 + 6 + 4 = 20
2 + 8 + 3 + 7 = 20
3 + 9 + 6 + 2 = 20

Introduction

In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set {−7, −3, −2, 5, 8}, the answer is yes because the subset {−3, −2, 5} sums to zero. The problem is NP-complete.

General info

Main complexity depends on N (number of input numbers, e.g. array length) and P (precision, it's just a number of binary values which represents numbers as discrete values). (note: This N and P have different meaning than NP problem ).

  • When N is small - just use exhaustive search
  • When P is small - use dynamic programming algorithms

Known solutions

Current solution: Recursion

Run recursion solution in nodejs

node case_rec.js

Code:

/**
 * Recursive approach
 * Time complexity - O(2^n)
 * Space complexity - O(n), take into account additional stack memory and memory for subsets
 */
const arr = [17, 2, 8, 34, 4, 0.5, 42, 6, 3, 7, 15, 14, 9]
const sum = 20

let result = null
function subset_sum(numbers, target, partial) {
    let s, n, remaining

    partial = partial || []
    s = partial.reduce( (a, b) => a + b, 0)

    if (s > target || partial.length > 4) return null
    
    // check if the partial sum is equals to target
    if (s === target && partial.length == 4) {
        if(!result) result = []
        result.push(partial)
        // console.log("%s=%s", partial.join("+"), target)
    }

    for (let i = 0; i < numbers.length; i++) {
        n = numbers[i]
        remaining = numbers.slice(i + 1)
        subset_sum(remaining, target, partial.concat([n]))
    }

    return result
}

// lets calculate time
const startTime = process.hrtime()
const res = subset_sum(arr, sum)
const diff = process.hrtime(startTime)

console.log(`Result:`, res)
console.log(`Time: ${ (diff[0] * 1e9 + diff[1]) / 1000000} ms`)

Issues:

  • It slowers down when n > 55

Notes:

  • We can't do array preparations (filter or sort etc. array) before run algorithm because it increases time and memory consumption. Also array can include negative numbers which excludes filtering numbers bigger than target S.
  • Node.js uses JavaScript VM and it is known that it badly works with float numbers - precision, number type convertions, overflows
  • To calculate timings hrtime (high-precision timer) was used

This solution uses a recursive combinations of all possible sums and picking which are equal to S. This algorithm generates many branches with combinations and test them if they reach the target (S), so if N or S are big - it is better to use other algorithm.

Further reading

Links helped to find possible solutions