Dynamic Programming with variable dimensions

Question

Resently I encountered this problem:

Given a set of unique base integers and a target value, return the combination of base integers which add up to the target value. The returned combination has to have the least amount of elements.

Example 1.
    Given: baseIntegers = [4, 7]; target = 15;
    Return: [7, 4, 4]
    Explanation: 7+4+4=15.

Example 2. 
    Given: baseIntegers = [3, 5, 7]; target = 18;
    Return: [7, 5, 3, 3]
    Explanation: 7+5+3+3=18. [3, 3, 3, 3, 3] is not returned since it contains 1 more element than [7, 5, 3, 3]

Example 3.
    Given: baseIntegers = [5, 6, 8, 11]; target = 52;
    Return: [11, 11, 11, 11, 8]
    Explanation: 11+11+11+11+8=52.

Example 4.
    Given: baseIntegers = [2, 5]; target = 3;
    Return: []
    Explanation: 2,5 do not add up to 3.

For example 1, I came up with an approach to solve the question using Dynamic Programming. Without going into much details, I created a 2-dimentional array to store the sum of the base integers:

    sum[0,0] = 0
    sum[1,0] = sum[0,0]+4 = 4
    sum[1,1] = sum[1,0]+7 = 11
    sum[2,1] = sum[1,1]+4 = 15

... When I found the target sum, I retrieve the result from the dimensions [2,1] (2 fours and 1 seven).

I can do example 3 in similar fashion by creating a 4-dimentional array.

However, I'm stuck if I need to solve the problem without knowing the length of baseIntegers ahead of time. The reason is that I can not create a multi-dimensional array without knowing its dimension beforehand. So here is my problem: Is there any way to solve this problem with variable input length? Preferablly with java, thanks!

Answer 1

First of all if you want to create a variable dimension array, you can simply create an interface. Something like this.

public interface MultiDimArray {
    int dim;
    int get (int[] idx);
    void set (int[] idx, int value);
    MultiDimArray getAll (int[] partialIdx);
    void setAll(int[] partialIdx, MultiDimArray values);
}

Then you create three subclasses that can be actually implemented.

1. A HigherMultiDimArray whose dimension is 2+.
2. A OneDimArray whose dimension is 1, and is where data is actually stored.
3. A ZeroDimArray whose dimension is 0, is basically a wrapper around an int, and which exists to give OneDimArray something to return at need.

This will let you declare an array of any dimension.

BUT you will find that a 10-dimensional array with 10 values per dimension takes 10 billion elements and you'll run out of memory.

---

Therefore I would recommend that you find a one dimensional structure to answer the questions:

1. How many values do we need to get to value x?
2. What is a last value that got us there?

And now you're dealing with a manageable amount of data. It isn't hard to use "dynamic programming" to figure out how to get this reasonably.

If you are clever about using something called A* Search, you can make getting this even faster.