# Reverse lookup of data based on user input

I have an array in the format:

``````\$array = array(
0 => array(
'name' => 'Item 1',
'level' => 1,
'points' => 10
),
1 => array(
'name' => 'Item 1',
'level' => 2,
'points' => 12
),
...
24 => array(
'name' => 'Item 1',
'level' => 25,
'points' => 100
),
25 => array(
'name' => 'Item 2',
'level' => 1,
'points' => 10
),
26 => array(
'name' => 'Item 2',
'level' => 2,
'points' => 12
),
...
34 => array(
'name' => 'Item 2',
'level' => 10,
'points' => 30
),
...
97 => array(
'name' => 'Item 10',
'level' => 1,
'points' => 14
),
...
108 => array(
'name' => 'Item 10',
'level' => 12,
'points' => 200
),
...
324 => array(...)
);
``````

1. Each "Item" has varying levels, for example, "Item 1" has 24 levels, but some Items can have up to 30 levels.
2. Points are not incremental or derived by a (known) formula.
3. There are 324 total "Items" lines in the reference data (18 Items with varying levels).

The user will input a point number of, say 8000, and this data array need to somehow give me a list of combinations of at most one of each "Item", but not necessarily one of each "Item" where the sum of points for these "Items" add up to exactly 8000 points.

The only way I can think of is to make a sort-of rainbow table with point values in it for each possible combinations, as an attempt at recursion made my machine ran out of memory.

For your reference, the number of levels for the 18 "Items" (in no particular order) are:

`30, 25, 20, 15, 1, 1, 3, 1, 3, 20, 25, 30, 30, 30, 30, 30, 20, 10 = 324` Levels.

I am not sure of the math, but I think there will be `30 * 25 * 20 ... * 20 * 10` rows in the table, so not sure that is feasible or possible.

How would I tackle this problem to get a result (if any) that matches user's input points?

• If I'm reading this right, this sounds like the subset sum problem. Do the solutions on that wikipedia page help? May 21, 2016 at 20:36
• Hi @lxrec! Thanks! I have skimmed through your article reference... It sure seems like what I am dealing with. The math behind it is way over my head, but I will definitely have to research that further; which I can, now that I know what it is called. Once I understand it, I can try and implement it programmatically. Thanks! No idea how to start, but at least I know where :-) May 22, 2016 at 13:03
• Glad I could help. If you hit a specific roadblock (before anyone posts an answer here), please edit your question to focus on that and then we can provide some more useful advice. The main reason no one's answered so far is that we probably can't add anything to what that wikipedia article already says, but we can definitely help with clarifying pieces of it or details it doesn't cover very well. May 22, 2016 at 13:35
• Hi @lxrec! You definitely got me on the right track, but I am afraid that this problem cannot be solved, really, because I do not have the hardware capable to handling these sheer numbers. I guess there is a reason why nobody ever published this tool for the online game I am playing; because it is infeasible to do this. I will upvote your comment, but I am abandoning the question. It is a good question though, and hence I do not want to delete it. Or should I? Someone might come up with something, sometime? Thoughts? May 25, 2016 at 11:11
• At the moment, as far as I know this question is effectively asking "How do I solve the subset sum problem?" which is thoroughly answered elsewhere and thus not of any great value here even though the topic is important. But it is on-topic and a far better question than most of the junk we get every day, so I don't see any real need to delete it. So I guess leave it as-is for now. May 25, 2016 at 11:14