Find all possible ways of representing a number n

During one of my recent interview with a giant software company, I was asked this question:

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. 

Some people might argue that tip 2 looks stupid, especially if you know that recursive is usually awful in terms of space complexity. Don't get me wrong here, the time complexity for a permutation style question is O(N!), factorial, and for a subset style question is O(2^N), exponential. But hey...this is not the side effect of recursive, but it is the nature that the space you have to search !! Yes, the space complexity is awful, and you may fix by Dynamic Programming or Iterative solution. However, what you need in the interview is not a perfect answer, but is to show you ability of coding, and analyzing complexity. And don't worry, if you get this simple answer quickly, they will ask you to improve it. That's the time for "iterative" solution.



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

1. Num(array, 8)  + 1 (we deal with 2)
2. Num(array, 7)  + 1 (we deal with 3)
3. Num(array, 5)  + 1 (we deal with 5)

So you get the big picture now, if we have an array that index is the "target", which is the remainder after we recursively call the function , and the value is the "# of possible combinations" we already know. We can simple sum them up.

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.