TRT
Sign in

Advanced · Module 15 · Lesson 5 of 6

Knapsack and subsets

Choosing a subset of items under a capacity is solved with a table over items and capacities. Whether each item can be used once or many times comes down to the direction of one loop.

Pro — members onlyAbout 15 minutes

By the end you can

  • Solve 0/1 knapsack with a table over capacity, and explain the take-or-skip recurrence
  • Distinguish 0/1 and unbounded variants by the direction of the capacity loop
  • Recognize subset sum, partition, coin change and counting variants, and explain pseudo-polynomial time

Builds on Grids and strings.

01 · A question first

You can carry 10 kg and must choose among 40 items with different weights and values. There are about a trillion possible selections. A table with one row per item and one column per kilogram finds the best selection in about 440 cells. Why does the capacity, rather than the number of selections, decide the cost?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Choosing a subset under a limit
  • The table
  • Unbounded: the loop turns around
  • Subset variants
  • Two-dimensional capacities and other twists
  • Pseudo-polynomial time
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeCoin changeFind the fewest coins that make an amount, with unlimited copies of each coin, using an unbounded knapsack table.Practice · medium · LeetCodePartition equal subset sumDecide whether an array can be split into two equal-sum halves, as a subset-sum table with a downward loop.Practice · medium · LeetCodeTarget sumCount the ways to assign + and − signs to reach a target, by transforming it into counting subsets with a given sum.Practice · medium · LeetCodeCombination sum IVCount the ordered sequences of numbers that sum to a target, and see how the loop order decides whether orderings are counted.

Asked in interviews

Something wrong with this lesson? Report a problem