1

I had a technical phone interview and I was doing well until i was asked this question. I was totally lost i had very little idea on how to solve such a problem.

You are given the following inputs: Total Score, Number of Players, Scores by each player. Sample Input would be

10 4 3 5 5 7

Where

10 = Total Score

4 = 4 players

3 = Score by player 1

5 = Score by player 2

5 = Score by player 3

7 = Score by player 4

You are to print out any combination that equals the total score. For instance we know player 4 and player 1 can have combine score of total score 10. So output for the above answer would be

1 4

1 = INDEX of player 1 4 = INDEX of player 4. Yes i know index of player 1 is technically 0 but they said print it out as such. If no combination matched you can print out none or anything you like . That didn't matter.

MY ATTEMPT

Well rather than being silent i first told interviewer i can use brute force approach to solve this. He said of course but we need better run time.

So i started thinking we could find all the possible combinations that could lead the total dollar and use MEMOIZATION to store the previously stored values. I was not able to think of a way of generating all combos and so i got stuck there.

Update He also mentioned the maximum score i can give you is 1000. I am not even sure why this matters?

I would appreciate if someone can stir me in right direction or even provide pseudo/working java sample of how to solve such a problem. I think this is a generic problem and i really wanna understand how to solve this problem

user1010101
  • 2,062
  • 7
  • 47
  • 76

1 Answers1

2

This is the subset sum problem, and assuming your scores are relatively small integers, it can be solved in pseudo-polynomial time using DP:

D(i,0) = 1
D(0,x) = 0     x > 0
D(i,x) = D(i-1, x) + D(i-1, x-arr[i])

The above recursion formulas will generate the matrix of size total_score X num_players. The number of possible combination is denoted in the bottom right entry of the matrix.

The idea is to mimic an exhaustive search, for each person you can either add it or not add it, and invoke the recurse to a smaller problem.

Pseudo code for DP solution:

Input:
let W be the total score
let arr be the array of players scores
let n be the size of arr
Pseudo Code:
declare 2d array D of size W+1 X n+1
//initialization of "borders":
for each i from 0 to n+1:
    D[i][0] = 1
for each x from 1 to W+1
    D[0][x] = 0
//the DP:
for each i from 1 to n+1:
   for each x from 1 to W+1:
       if arr[i] < x:
          D[i][x] = D[i-1][x]
       else:
          D[i][x] = D[i-1][x] + D[i-1][x-arr[i]]
//by here you have the matrix D filled up
//the wanted value is D[n][W]
return D[n][W]
amit
  • 175,853
  • 27
  • 231
  • 333