Given a list of integers,our task is to find if a sub-sequence which adds to a given number exists or not.

**Example-**

The given list is (1,4,20,5,5) and the given number or sum is 29.

Then,the sub-sequence which adds to 29 is (4,20,5).

**Brute Force-**

All the sub-sequences are considered and its sum is compared with the given value.Its time complexity is O(N^2).

**Code-**

[cpp]

//arr[0…N-1] contains the given integers

// and the given number is X.

for(i=0;i<N;i++)

{

s=arr[i];

for(j=i+1;j<N;j++)

{

s=s+arr[j];

if(s==X) return 1; // sub array found

}

}

return 0; //sub-array not found

[/cpp]

**Efficient Code-**

**Algorithm-**

1. Initialize a variable curr_sum as first element.

2. Start from the second element and add all elements one by one to the curr_sum.

3. If curr_sum becomes equal to X, then a sub-sequence/sub-array is found.

4. If curr_sum exceeds X, then remove trailing elements one by one until curr_sum is less than X.

Its time complexity is O(N).

**Code-**

[cpp]

{

curr_sum=arr[0];

start=0;

for (i = 1; i <= n; i++)

{

// If curr_sum exceeds X, then

// remove the starting elements

while (curr_sum > X && start < i-1)

{

curr_sum = curr_sum – arr[start];

start++;

}

// If curr_sum becomes equal to X,

// then return true

if (curr_sum == X)

{

return 1; //sub-array found

}

// Add this element to curr_sum

if (i < n)

curr_sum = curr_sum + arr[i];

}

return 0; //sub-array not found

}

[/cpp]