Question
|
Difficulty Level:
5
|
Solution
|
Explanation Quality:4.7
|
This is a very interesting question. Let's start with a sample array. Say we are
given the following array:
So the problem is asking that if we are given a target number = 17 can we find one
possible set of integers in the given array which would make up this target number.
In the given array we would can make up 17 using 1, 3, 6 and 7. Another possible
set is 8 and 9.
The brute force solution would be to find all the possible combinations starting
from length 1 upto the total length of the array, and finding the sum of each combination
to find if it equals the target.
The other solution we can understand better if we restrain ourselves to find just
two integers which add up to our target. So the first step is that we sort our given
array. Note that the sample array I gave is already sorted. Once we sorted the array
we pick the first number which is 1 in our case and subtract it from our target
which is 17. The result is 16. Now since our array is sorted we just perform a binary
search on the array looking for 16. The search would take O(lgn) time and since
in the worst case we can scan through the entire array and at every step we would
be performing the binary search the total time is O(nlogn). This is also the solution
incase you are asked that two integers should add upto the target.
So now let's see how we can generalize to any number of integers. By generalization
we mean that we are not limiting ourselves to just two integers, we are just trying
to find as many integers as it takes to add up to the target. For instance if target
= 20 then we in our given array no two integers add upto 20 however 1, 3, 7 and
10 would add upto 20 and we would write an algorithm that does just that.
The key here is to think in recursive terms. Say we start off the usual way that
we subtract 1 from 20 and get 19. We immediately conduct a binary search on the
rest of the array to figure out if a 19 exists and it doesn't. So now we question
is there a way to make up 19 from the rest of the array numbers? Note that you are
actually asking a recursive question. If we could make up 19 then we would add our
starting number 1 to it and make up 20 and thus answer yes to our intial question
that we could indeed make up 20 from the original array.
Let's see what happens at the second level of recursive algorithm. We know we have
used 1 and we are looking to make a 19 from the rest of the array so again apply
the same algorithm by making our target 19 but this time our array would be one
elment short that is 1 would not be included in our search since we have already
used it. Now we subtract 3 from 19 getting a 16. We search the passed in array to
look for a 16 but again it doesn't. Note if it did we would add it to our list of
integers and return success. However since it failed we again make a recursive call
to our function, this time with target as 16 and we pass in an array two elements
short that is without 1 and 3 since we have used them.
At our third level of recursion, we subtract 5 from 16 to get an 11. We would again
make recursive calls with target 11 and passing in the array with the unused integers
that is without 1,3 and 5. This track would eventually fail. So we would come back
to our third level of recursion, and try the next element in the array which is
6. So we subtract 6 from the target at the third level of recursion which is 10
and we again make a recursive call here but note that when we are passing the array
to the fourth level of recursion we would include 5 in it since the integers now
being used are 1, 3 and 6. This track would fail too.
Finally we try element 7 at the third level of recursion. We subtract 7 from 16
to get a 9. We go to the fourth level of recursion with target = 9 and the array
we input would be 5, 6, 8 and 9. We conduct our binary search, find 9, include it
our integer list and return success. This travels up all the way back and we are
back to the first time we made a recursive call with target as 20. We print out
success. Here's a pseudocode for the above algorithm.
target = 20;
ListOfIntegers List;
Array[] = {1, 3, 5, 6, 7, 8, 9};
Sort(Array);
bool findIntegers(int[] Array,int target){
int index = BinarySearch(Array, target);
if(index){
List.Add(Array[index]);
return success;
}
foreach(element in Array){
bool found = false;
List.Add(element);
Array = Array without element;
found = findIntergers(Array,target - element);
if(found)
return success;
}
else{
List.Remove(element);
}
}
}
The function BinarySearch would return the index of the target if it is found in
the array and false if it isn't found. At the end List would contain all those integers
which make up the target if the findIntegers function returns successfully.
|