Find sub-array whose sum equal to a given number

Given an array of non negative ints, is it possible to choose a sub array, such that the sum is equal to the given target?

Example:
Input : arr[] = {2, 4, 8}, target = 12
Output : true.(because 4+ 8 = 12(target sum))

Input : arr[] = {2, 4, 8}, target = 10
Output : false.(because we can’t achieve target sum by any continuous subarray)

Method 1:

This method will find out if there exist a sub array with sum equal to given target, returns true or false.

```bool isGroupSum(int *arr, int target, int start){
/*Base condition*/
if(start >= arr.length)
return (target == 0);

/*we found the target sum, return true*/
if(target == 0)
return true;

/*else, check if sum can be obtained by any of the following
1) Including the current element
2) Excluding the current element*/
return isGroupSum(arr, target - arr[start], start+1)
|| isGroupSum(arr, target,start+1);
}
```

Method 2:

This method will find sub array with given target sum. A simple solution is to consider all subarrays one by one and check the sum of every subarray. Run two loops: the outer loop picks a starting point i and the inner loop tries all subarrays starting from i. More efficient solution will be in O(N) time.

Initialize a variable rem_sum as first element. rem_sum indicates the sum of current sub-array. Start from the second element and add all elements one by one to the rem_sum. If rem_sum becomes equal to sum, then print the solution. If rem_sum exceeds the sum, then remove trailing elements while rem_sum is greater than sum.

```int getGroupSum(int *arr, int n, int target)
{
int rem_sum = arr[0], start = 0, i;
for (i = 1; i <= n; i++)
{
while(rem_sum > target && start < i-1)
{
rem_sum = rem_sum - arr[start];
start++;
}
if(rem_sum == target)
{
printf ("Sum found between indexes %d and %d", start, i-1);
return 1;
}
if(i < n)
rem_sum = rem_sum + arr[i];
}

printf("No sub array with target sum");
return 0;
}
```

Time Complexity: O(N)

2 Thoughts on “Find sub-array whose sum equal to a given number”

1. Anuj Siroi on August 25, 2013 at 11:13 am said:

The program doesn’t work. Even the logic seems to be absurd. Even for the given array {2, 4, 8} the program gives false (0) result. And from the next time, please try to write the whole program instead of writing just a part of the program.

• crazyadmin on August 25, 2013 at 1:02 pm said:

Hi Anuj,

Example quoted above was wrong. Now it has been corrected. You can check by writing a simple driver function to test above.