Dynamic Programming Board Problem — Subset Sum

Work in small groups for 10 minutes.

You are given the set:

S = {3, 5, 6}

Can you make the target sum:

T = 9

using each number at most once?

DP Meaning

dp[i][j] = true if we can form sum j using the first i numbers
(numbers in order: 3, 5, 6)

Base Cases

• dp[0][0] = true
• dp[0][j] = false for j > 0

Recurrence

Let the i-th number be w_i

• If j<w_i
  dp[i][j] = dp[i−1][j]
• Otherwise:
  dp[i][j] = dp[i−1][j] OR dp[i−1][j − w_i]

DP Table (mostly blank — fill it in)

                0   1   2   3   4   5   6   7   8   9
             -------------------------------------------
0 items       | T | F | F | F | F | F | F | F | F | F
3             | T |   |   | T |   |   |   |   |   |  
5             | T |   |   |   |   |   |   |   |   |  
6             | T |   |   |   |   |   |   |   |   |  

(Only the first column is filled for rows 1–3, and two starter truths for the “3” row.)

Questions

1. Fill in the entire table.
2. Is dp[3][9] true or false?
3. If true, what subset achieves 9?