Given an array of integers and a target integer, write a method groupSumWithNum
to determine if it is possible to choose
a group of integers from the array such that the group sums to the given target. An additional
constraint is that the summation must include the integer must_have
if it is
present in the array.
groupSumWithNum({1,2,3,6,5},5,10) ==> true
groupSumWithNum({1,2,3,6,5},3,7) ==> false
start_index
and keep subtracting it from the target
to reach the base condition. The key here is to include the must_have
integer as part of the target.
The idea is to recursively select each element and see if it can be used to reach to the target.
1. If start_index >= length of the array
, return true
when the target is zero, false
otheriwse.
2. If the element at the start index is equal to must_have
, recurse by subtracting that element from the target. i.e. return groupSumWithNum(start_index+1,arr,must_have,target-must_have);
3. Include the first number and check the remaining numbers. i.e. groupSum(start_index+1,arr,target-arr[start_index]))
4. Exclude the first number and check the remaining numbers. i.e. groupSum(start_index+1,arr,target)
public static boolean groupSumWithNum(int[] arr, int must_have, int target) { }
C
Java
Python