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)
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.
Hi Anuj,
Example quoted above was wrong. Now it has been corrected. You can check by writing a simple driver function to test above.
The first code checks if there is a subset with a given sum not a sub-array. For instance it returns true for {3, 2, 8} and sum = 11 even there isn’t such a sub-array.
Also, the second code checks for sub-array with sum but will only work when all the elements in the array are positive.
Please put the corrections in this post.