algorithm - Find a subset with sum within a range -

how can find subset of array sum of elements within given range?

for example:

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

so b potentially [1, 1, 3], [1, 3], [3], [1, 3]; doesn't matter order need 1 of them.

you use dynamic programming approach solve problem.

let f[i][j] have value true if possible select numbers among numbers original subset a[1..i] sum equal j.

i vary 1 length of a, , j 0 max inclusively, max second number given range.

f[i][0] = true i definition (you can select empty subset).

then f[i][j] = f[i - 1][j - a[i]] | f[i - 1][j]

logically means if can select subset sum j elements 1..i-1, can subset 1..i, , if can select subset sum j - a[i] elements 1..i-1, adding new element a[i] subset, can desired sum j.

after have calculated values of f, can find f[n][j] true values j lying in desired range.

say have found such number k. algorithm find required set that:

for = n..1:     if f[i - 1][k - a[i]] == true          output a[i] answer          k -= a[i]          if k == 0              break