I want to solve the decision subset sum problem, so finding if a given set of integers has a subset that adds up to some T.
In the algorithm ordered arrays are sequentially searched through using the binary search algorithm.
I want to know whatbthe runtime of the algorithm is. i imagine its pseudo polynomial but i am not sure
Consider an ordered set S of integers [S1,S2,S3,...,Sn]
The algorithm i want to use will perform sums of particular combinations of elements. Note the array is never actually stored. You can assume that the binary search is an effective method because the sets of sums are ordered. So you are always performing at most log_2(n)sums
First consider the ordered array [S1+ S2, S1+S3,...,S1+Sn] And binary search through these sums to see if T is equal to any of the elements. Because the array is ordered, the binary search is effective
Then consider the array [S2+ S3, S2 +S4,...,S2+Sn] And similarly binary search through that.
Repeat this process until you have exhausted through all possible Sx up to Sn-1 in this way .
Then the algorithm will move onto a second loop which will start with a condensed set of [(S1+ S2)+ S3, (S1+S2) + S4,...,(S1+S2) + Sn] Again we can check fora sum T in this array using a binary search because she set is ordered .
Repeat this binary search for the next array im the sequence with the form [(S1+ S3)+ S4, (S1+S3) + S5,...,(S1+S3) + Sn]
repeat for all (S1+ Sx)+ Sn until x = n-1
Then the next array to consider is [(S2+ S3)+ S4, (S2+S3) + S5,...,(S2+S3) + Sn]
and then [(S2+ S4)+ S5, (S2+S4) + S6,...,(S2+S4) + Sn]
and so in the same manner. This way you exhaust all the possoble 3 element sum combinations
You can the repeat for all the possible 4 element sum combinations in the same way starting with [(S1+S2+ S3)+ S4, S1+S2+ S3)+ S5,....,S1+S2+ S3)+ Sn]
and in this way you can iterate through all possible subsets.
I tried using chatgpt to analyse the run-time and failed.