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.

Leave a Reply

Your email address will not be published. Required fields are marked *

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=""> <strike> <strong>

Post Navigation