CODEWITHSUNDEEP
algorithmmath
luis
luis

Reputation: 2305

Find a subset with sum within a range

How can I find a subset of an array that the sum of its elements is within a given range?

For example:

let a = [ 1, 1, 3, 6, 7, 50]
let b = getSubsetSumRange(3, 5)

so b could potentially be [1, 1, 3], [1, 3], [3], [1, 3]; It doesn't matter the order I only need one of them.

Upvotes: 1

Views: 1623

Answers (1)

Alexey Subach
Alexey Subach

Reputation: 12312

You would probably like to use dynamic programming approach to solve this problem.

Let F[i][j] have value true if it is possible to select some numbers among numbers from the original subset a[1..i] so that their sum is equal to j.

i would obviously vary from 1 to length of a, and j from 0 to max inclusively, where max is the second number from your given range.

F[i][0] = true for all i by definition (you can always select empty subset).

Then F[i][j] = F[i - 1][j - a[i]] | F[i - 1][j]

Logically it means that if you can select a subset with sum j from elements 1..i-1, then you obviously can do it with the subset 1..i, and if you can select a subset with sum j - a[i] from elements 1..i-1, then by adding your new element a[i] to that subset, you can get your desired sum j.

After you have calculated the values of F, you can find any F[n][j] that is true for values j lying in your desired range.

Say you have found such number k. Then the algorithm to find the required set would look like that:

for i = n..1:
    if F[i - 1][k - a[i]] == True then
         output a[i] to the answer
         k -= a[i]
         if k == 0
             break

Upvotes: 2

Related Questions