Given an array of integers and a target number, determine if it is possible to choose a group of integers from the array, such that the numbers in the group sum to the given target.
groupSum({1,2,3,6,5},10) ==> true
groupSum({1,2,3,6,5},18) ==> false
The idea is to recursively select each element and check if it can be used to reach to the target.
1. If start_index >= length of the array
, return true
when target
is zero, false
otheriwse.
2. Include the first number and check the remaining numbers. i.e. groupSum(start_index+1,arr,target-arr[start_index]))
3. Exclude the first number and check the remaining numbers. i.e. groupSum(start_index+1,arr,target)
public static boolean groupSum(int[] arr, int target) { }
C
Java
Python