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);
}
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