# Subarray with given sum

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-

```
//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
}
}
```

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-

```{
curr_sum=arr;
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];
}
}

```

You may use these HTML tags and attributes: `<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> `