Given an unsorted set of integers in the form of array, find all possible subsets whose sum is greater than k1 and less than k2 ,where k1 ,k2 are two floating constants, eg:- Our set is {2,3,5,8,10} and k1 =10 and k2 = 12.
Possible subsets:-
{2,3,5}
{8,2}
{8,3}
{10}
{10,2}
I can only think of a naive algorithm, is there any better method or similar problems ,please give some suggestions. It is actually an important part of my project work? Is there any dynamic programming method available ?
Yes, dynamic programming method does exist.
Make table (array of lists) with length k2+1 and fill it:
For every value V=A[i] scan array from the end to beginning, and add V to the list in j-th cell, if Table[j - V] is not empty (so we can compose value j adding V to all subsets from Table[j - V])
At the end check cells with needed sums and restore sequences.
Example for 2,3,5:
0 1 2 3 4 5 6 7 8 9 10 //index
[0] //initial state
[0] [2] //after 2
[0] [2] [3] [3] //after 3
[0] [2] [3] [3,5] [5] [5] [5] //after 5
To retrieve sets for sum 5 - got to the fifth cell and unwind values to the left.
3 denotes we go to 5-3=2, then use 2 until zero entry. Second variant - with 5 we go to zero entry. So value 5 might be produced from set {5} or from set {3,2}
Note that storing data for sequences might require a lot of space, and restoring sequences might require up to 2^N time - when there are many good subsets.