Thursday 15 August 2013

Group Sum

Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target?

Example:

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

Input : arr[] = {2, 4, 8}, target = 9
Output : false.(because we can't achieve target sum by any combination of array elements) 


Solution:

boolean isGroupSum(int start, int []arr, int target){
      /*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(start+1, arr, target - arr[start]) 
               || isGroupSum(start+1, arr, target);
}

No comments:

Post a Comment