Subset sum, coin change and rod cutting

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Matrix-chain split cost? from Lesson 5.2.1
• LCS time? from Lesson 5.1.3
• Greedy coin change on {1, 3, 4} for 6? from Lesson 4.2.4

1 · The Hook

🎣

"Can some of these numbers add up to exactly 9?" "In how many ways can you pay ₹12 with coins of 1, 2, 5, 10?" "How should a steel rod be cut to sell for the most?" These are DPs where the table is indexed by an amount. They show up in GATE as NAT questions with small numbers.

2 · Predict First

🤔

Coins 1, 2 and 5 (unlimited). In how many ways can you make 5, ignoring order?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

5; 2 + 2 + 1; 2 + 1 + 1 + 1; 1 + 1 + 1 + 1 + 1: 4 ways.

Subset sum

Is there a subset of S that sums to t? R[x] = true if some subset of the items seen so far sums to x. For each item s: for x from t down to s: R[x] = R[x] or R[x − s]. Θ(n·t) (pseudo-polynomial). Counting subsets uses + instead of "or".

Coin change: number of ways (order ignored)

W[0] = 1. For each coin c, for x from c to the amount: W[x] += W[x − c]. Putting the coin loop outside counts combinations (2 + 1 and 1 + 2 once). Swapping the loops would count ordered sequences.

Coin change: minimum coins

D[0] = 0; D[x] = 1 + min over coins c ≤ x of D[x − c]. Θ(amount × number of coins). Correct for any coin system, unlike greedy.

Rod cutting

A rod of length n; price pᵢ for a piece of length i. R[j] = max over i ≤ j of (pᵢ + R[j − i]), R[0] = 0. Θ(n²). Prices (lengths 1–8): 1, 5, 8, 9, 10, 17, 17, 20. R[4] = 10 (2 + 2); R[8] = 22 (2 + 6).

4 · Visual

Coin ways for amount 5 with coins {1, 2, 5}

x:            0  1  2  3  4  5
start:        1  0  0  0  0  0
after coin 1: 1  1  1  1  1  1
after coin 2: 1  1  2  2  3  3
after coin 5: 1  1  2  2  3  4     -> 4 ways

5 · Worked Examples

Example 1 Easy

Is there a subset of {3, 34, 4, 12, 5, 2} with sum 9?

Solution

Yes: 4 + 5 (or 4 + 3 + 2).

Example 2 Medium

Minimum coins to make 27 with coins {2, 5, 10}?

Solution

10 + 10 + 5 + 2 = 4 coins.

Example 3 GATE

Rod prices (lengths 1–8): 1, 5, 8, 9, 10, 17, 17, 20. Maximum revenue for a rod of length 8?

Solution

22: cut into 2 + 6 (5 + 17).

6 · GATE Traps

⚠️

• Coin-ways: coins in the outer loop count combinations; amounts outer counts permutations.
• 0/1 subset sum loops amounts downward; unlimited coins loop upward.
• Minimum coins needs DP when the coin system is not canonical.
• Rod cutting allows no cut (selling the whole rod) as one option.

7 · Memory Hook

🧠

"Index the table by the amount left to reach."

8 · Connect the Dots

These DPs index by amounts. The last DP lesson indexes by positions in sequences again: longest increasing subsequence and edit distance.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksCoin ways

Number of ways to make 10 with coins {2, 3, 5, 6} (order ignored)?

Numerical answer: ________

Q2NAT2 marksCoin ways

Number of ways to make 12 with coins {1, 2, 5, 10} (order ignored)?

Numerical answer: ________

Q3NAT1 markMin coins

Minimum coins to make 11 with {1, 5, 6, 9}?

Numerical answer: ________

Q4NAT2 marksRod cutting

Rod prices (lengths 1–8): 3, 5, 8, 9, 10, 17, 17, 20. Maximum revenue for length 8?

Numerical answer: ________

Q5NAT2 marksSubset count

Number of subsets of {2, 3, 5, 6, 8, 10} that sum to 10?

Numerical answer: ________

10 · Rule Card

• Subset sum: R[x] |= R[x − s], x downward; Θ(n·t). Counting: +=.
• Coin ways: coins outer, amounts upward: W[x] += W[x − c].
• Min coins: D[x] = 1 + min D[x − c].
• Rod cutting: R[j] = max(pᵢ + R[j − i]); Θ(n²).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

subset sum DPcounting subsetscoin change (number of ways)combinations vs permutations loop orderminimum-coin DProd cutting

12 · Answer Vault