The solution is pretty simple and straightforward.
Say we are doing this for index i.
We generate the subsequences by extending our subsequence outside the limits(indices) x[i] and i because the subsequence will always take elements of array from x[i] to i and if we only expand, our subsequnce will always have the indices x[i] and i.
But of course, we will also cover the obvious subsequence from x[i] to i which is the very first subsequence.
EDIT:To avoid duplicates, we must check whether the given combination of left and right boundaries have been tried or not.
For this we will make an adjacency list which will contain
N linked lists.
and all linked lists are initially empty.
Now a given subsequence with corresponding left and right boundaries have not been tried before if and only if
linked list arr[left] does not contain element right.
If linked list arr[left] contains element right then it means the subsequence has been printed before.
First we fix left boundary of our subsequence to be x[i] and then with new left boundary we try all possible new right boundaries which are:
i,i+1,i+2 ....... N-1 , N is equal to length of array a. Corresponding subsequenes being if(a[j] linked list does not contain i) { print the subsequence a[j],a[j+1],......a[i] add i to arr[j] } if(a[j] linked list does not contain i+1) { print the subsequence a[j],a[j+1],.........a[i+1] add i+1 to a[j] } and similar if condition before all subsequences given below. a[j],a[j+1],...............a[i+2] . . a[j],a[j+1]..........................a[N-1] j is x[i] for the above subsequences.
Then we fix left boundary to be x[i]-1 and then with new left boundary we try all possible new right boundaries which are:
i,i+1,i+2 ....... N-1
Corresponding subsequenes being
similar if condition as given above before all subsequences given below. and they will be printed if and only if the condition is true. a[j],a[j+1],.........a[i] a[j],a[j+1],...............a[i+1] . . a[j],a[j+1]..........................a[N-1] j is x[i]-1 for the above subsequences.
We do this till j becomes 0 and that will be the last iteration.
Now coming to the efficiency of this algorithm, because at every step I am generating a new subsequence,and none of the steps go wasted in producing a subsequence that does not include both indices so I think it is pretty much efficient.
i=0should I count 5 segments, but fori=1there are none?