Given an array of numbers, find all possible ways of representing a number n. For example, let's assume we have [2, 3, 5] in an array, and the target number is 10.Well... I fail this interview in that I'm trying to work out a iterative solution given the stressful condition. I went home and I suddenly realize this is a manageable problem as long as I'm not greedy.
- Tip 1: for all "combination" / "subset" questions, you should always start with hacking a recursive solution, because it's the most intuitive one.
- Tip 2: never try to provide the "best" answer to your interviewer. Don't worry, they will challenge you and ask you to propose a better answer later.
Here is the simple way of doing it:
import java.util.ArrayList;
import java.util.Arrays;
public class FindAllComb {
public static void main(String[] args) {
int[] ar = {3,5, 2};
printCombForN(ar,10,0, new ArrayList());
}
//try = 0, meaning we start from the first element in the array
public static boolean printCombForN(int[] ar, int target, int idx, ArrayList buffer){
//base case: if no more choice
if(target == 0) {
return true;
}
else if (target < 0) {
return false;
}
// for all possible choice
for(int i=idx; i < ar.length; i++){
//make a choice
buffer.add(ar[i]);
target-=ar[i];
if (printCombForN(ar, target, i, buffer)){
//print buffer
System.out.println(Arrays.toString(buffer.toArray()));
}
//unmake the choice
buffer.remove(buffer.size() -1);
target += ar[i];
}
return false;
}
}
It may looks hard at its first glance but essentially this is a simple back-tracking problem. For back-tracking problem, here is the template I follow: bool Solve(configuration conf) //Credit: Zelenski, Julie
{
if (no more choices) // BASE CASE
return (conf is goal state);
for (all available choices) {
try one choice c;
// solve from here, if works out, you're done
if (Solve(conf with choice c made)) return true;
unmake choice c;
}
return false; //tried all choices, no soln found
}
Can we do better?
Yes, with the help of DP.
The idea is that we can "memorize" things we did before.
For example, if we know th only possible choice of making 5 are (2,3) or (5), we can simple save it in a HashMap so that we don't have to go over same path again.
So let's slightly change the problem, what if we don't need you to print all possible combination, but we just want you to return number of possible combinations?
The idea here is Num(array, 10) = the sum of the following
- Num(array, 8) + 1 (we deal with 2)
- Num(array, 7) + 1 (we deal with 3)
- Num(array, 5) + 1 (we deal with 5)
I will add answer later, but one thing you should keep in mind is that to make things faster, often times the price is space. In this example, we need extra space for tracking counts. Though, here (the revised question) the cost is acceptable.
Note that all back-tracking problem can be accelerated by some heuristic pruning. That is, you may "return false" earlier if you know there's no way you can get a goal state along the path.
