- Introduction
- 0/1 Knapsack Problem
- Unbounded Knapsack Problem
- Subset Sum Problem
- Can Sum Problem
- How Sum Problem
- Best Sum Problem
- Complexity Analysis
Knapsack problems are a family of optimization problems where we need to select items to maximize value while respecting weight/capacity constraints. Dynamic Programming (DP) provides efficient solutions by breaking down the problem into overlapping subproblems.
Problem: Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value. Each item can be used at most once.
/**
* 0/1 Knapsack - Recursive Approach
* Time: O(2^n), Space: O(n) for recursion stack
*/
function knapsack01Recursive(weights, values, capacity, n = weights.length) {
// Base case: no items left or no capacity
if (n === 0 || capacity === 0) {
return 0;
}
// If weight of nth item is more than capacity, skip it
if (weights[n - 1] > capacity) {
return knapsack01Recursive(weights, values, capacity, n - 1);
}
// Return max of two cases:
// 1. nth item included
// 2. nth item not included
const include = values[n - 1] + knapsack01Recursive(
weights,
values,
capacity - weights[n - 1],
n - 1
);
const exclude = knapsack01Recursive(weights, values, capacity, n - 1);
return Math.max(include, exclude);
}
// Example usage
const weights1 = [1, 3, 4, 5];
const values1 = [1, 4, 5, 7];
const capacity1 = 7;
console.log(knapsack01Recursive(weights1, values1, capacity1)); // 9/**
* 0/1 Knapsack - Memoization (Top-Down DP)
* Time: O(n * W), Space: O(n * W)
*/
function knapsack01Memo(weights, values, capacity) {
const n = weights.length;
const memo = Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(-1));
function helper(n, cap) {
// Base case
if (n === 0 || cap === 0) {
return 0;
}
// Check memo
if (memo[n][cap] !== -1) {
return memo[n][cap];
}
// If weight exceeds capacity, skip item
if (weights[n - 1] > cap) {
memo[n][cap] = helper(n - 1, cap);
return memo[n][cap];
}
// Max of include/exclude
const include = values[n - 1] + helper(n - 1, cap - weights[n - 1]);
const exclude = helper(n - 1, cap);
memo[n][cap] = Math.max(include, exclude);
return memo[n][cap];
}
return helper(n, capacity);
}
// Example usage
console.log(knapsack01Memo(weights1, values1, capacity1)); // 9/**
* 0/1 Knapsack - Bottom-Up DP (Tabulation)
* Time: O(n * W), Space: O(n * W)
*/
function knapsack01BottomUp(weights, values, capacity) {
const n = weights.length;
const dp = Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(0));
// Build table bottom-up
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
// Don't include current item
dp[i][w] = dp[i - 1][w];
// Include current item if possible
if (weights[i - 1] <= w) {
const includeValue = values[i - 1] + dp[i - 1][w - weights[i - 1]];
dp[i][w] = Math.max(dp[i][w], includeValue);
}
}
}
return dp[n][capacity];
}
// Example usage
console.log(knapsack01BottomUp(weights1, values1, capacity1)); // 9/**
* 0/1 Knapsack - Space Optimized
* Time: O(n * W), Space: O(W)
*/
function knapsack01SpaceOptimized(weights, values, capacity) {
const n = weights.length;
let dp = Array(capacity + 1).fill(0);
for (let i = 0; i < n; i++) {
// Traverse from right to left to avoid overwriting
for (let w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
}
}
return dp[capacity];
}
// Example usage
console.log(knapsack01SpaceOptimized(weights1, values1, capacity1)); // 9Problem: Similar to 0/1 knapsack, but each item can be used unlimited times.
/**
* Unbounded Knapsack - Recursive
* Time: O(2^n), Space: O(W) for recursion
*/
function unboundedKnapsackRecursive(weights, values, capacity, n = weights.length) {
// Base case
if (capacity === 0 || n === 0) {
return 0;
}
// If weight exceeds capacity, skip
if (weights[n - 1] > capacity) {
return unboundedKnapsackRecursive(weights, values, capacity, n - 1);
}
// Include (can use same item again) or exclude
const include = values[n - 1] + unboundedKnapsackRecursive(
weights,
values,
capacity - weights[n - 1],
n // Note: n, not n-1 (can reuse)
);
const exclude = unboundedKnapsackRecursive(weights, values, capacity, n - 1);
return Math.max(include, exclude);
}
// Example usage
const weights2 = [1, 3, 4, 5];
const values2 = [10, 40, 50, 70];
const capacity2 = 8;
console.log(unboundedKnapsackRecursive(weights2, values2, capacity2)); // 110/**
* Unbounded Knapsack - Memoization
* Time: O(n * W), Space: O(n * W)
*/
function unboundedKnapsackMemo(weights, values, capacity) {
const n = weights.length;
const memo = Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(-1));
function helper(n, cap) {
if (cap === 0 || n === 0) {
return 0;
}
if (memo[n][cap] !== -1) {
return memo[n][cap];
}
if (weights[n - 1] > cap) {
memo[n][cap] = helper(n - 1, cap);
return memo[n][cap];
}
const include = values[n - 1] + helper(n, cap - weights[n - 1]);
const exclude = helper(n - 1, cap);
memo[n][cap] = Math.max(include, exclude);
return memo[n][cap];
}
return helper(n, capacity);
}
// Example usage
console.log(unboundedKnapsackMemo(weights2, values2, capacity2)); // 110/**
* Unbounded Knapsack - Bottom-Up DP
* Time: O(n * W), Space: O(n * W)
*/
function unboundedKnapsackBottomUp(weights, values, capacity) {
const n = weights.length;
const dp = Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
dp[i][w] = dp[i - 1][w]; // Exclude
if (weights[i - 1] <= w) {
// Include (use dp[i] not dp[i-1] for unbounded)
const includeValue = values[i - 1] + dp[i][w - weights[i - 1]];
dp[i][w] = Math.max(dp[i][w], includeValue);
}
}
}
return dp[n][capacity];
}
// Example usage
console.log(unboundedKnapsackBottomUp(weights2, values2, capacity2)); // 110/**
* Unbounded Knapsack - Space Optimized
* Time: O(n * W), Space: O(W)
*/
function unboundedKnapsackSpaceOptimized(weights, values, capacity) {
const dp = Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
// Traverse left to right (allows reuse)
for (let w = weights[i]; w <= capacity; w++) {
dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
}
}
return dp[capacity];
}
// Example usage
console.log(unboundedKnapsackSpaceOptimized(weights2, values2, capacity2)); // 110Problem: Given a set of non-negative integers and a sum, determine if there's a subset with sum equal to the given sum.
/**
* Subset Sum - Recursive
* Time: O(2^n), Space: O(n)
*/
function subsetSumRecursive(nums, sum, n = nums.length) {
// Base cases
if (sum === 0) return true;
if (n === 0) return false;
// If last element is greater than sum, skip it
if (nums[n - 1] > sum) {
return subsetSumRecursive(nums, sum, n - 1);
}
// Check if sum can be obtained by:
// 1. Including last element
// 2. Excluding last element
return subsetSumRecursive(nums, sum - nums[n - 1], n - 1) ||
subsetSumRecursive(nums, sum, n - 1);
}
// Example usage
const nums1 = [3, 34, 4, 12, 5, 2];
const sum1 = 9;
console.log(subsetSumRecursive(nums1, sum1)); // true (4 + 5)/**
* Subset Sum - Memoization
* Time: O(n * sum), Space: O(n * sum)
*/
function subsetSumMemo(nums, sum) {
const n = nums.length;
const memo = Array(n + 1).fill(null).map(() => Array(sum + 1).fill(null));
function helper(n, targetSum) {
// Base cases
if (targetSum === 0) return true;
if (n === 0) return false;
// Check memo
if (memo[n][targetSum] !== null) {
return memo[n][targetSum];
}
// If current element is greater than sum, skip it
if (nums[n - 1] > targetSum) {
memo[n][targetSum] = helper(n - 1, targetSum);
return memo[n][targetSum];
}
// Include or exclude
memo[n][targetSum] = helper(n - 1, targetSum - nums[n - 1]) ||
helper(n - 1, targetSum);
return memo[n][targetSum];
}
return helper(n, sum);
}
// Example usage
console.log(subsetSumMemo(nums1, sum1)); // true/**
* Subset Sum - Bottom-Up DP
* Time: O(n * sum), Space: O(n * sum)
*/
function subsetSumBottomUp(nums, sum) {
const n = nums.length;
const dp = Array(n + 1).fill(null).map(() => Array(sum + 1).fill(false));
// Sum 0 is always possible (empty subset)
for (let i = 0; i <= n; i++) {
dp[i][0] = true;
}
// Fill the table
for (let i = 1; i <= n; i++) {
for (let s = 1; s <= sum; s++) {
// Exclude current element
dp[i][s] = dp[i - 1][s];
// Include current element if possible
if (nums[i - 1] <= s) {
dp[i][s] = dp[i][s] || dp[i - 1][s - nums[i - 1]];
}
}
}
return dp[n][sum];
}
// Example usage
console.log(subsetSumBottomUp(nums1, sum1)); // true/**
* Subset Sum - Space Optimized
* Time: O(n * sum), Space: O(sum)
*/
function subsetSumSpaceOptimized(nums, sum) {
const dp = Array(sum + 1).fill(false);
dp[0] = true; // Empty subset
for (let i = 0; i < nums.length; i++) {
// Traverse right to left
for (let s = sum; s >= nums[i]; s--) {
dp[s] = dp[s] || dp[s - nums[i]];
}
}
return dp[sum];
}
// Example usage
console.log(subsetSumSpaceOptimized(nums1, sum1)); // trueProblem: Given a target sum and an array of numbers, return true if it's possible to generate the target sum using numbers from the array (can use elements multiple times).
/**
* Can Sum - Recursive
* Time: O(n^m) where m is target, Space: O(m)
*/
function canSumRecursive(target, nums) {
// Base cases
if (target === 0) return true;
if (target < 0) return false;
// Try each number
for (let num of nums) {
if (canSumRecursive(target - num, nums)) {
return true;
}
}
return false;
}
// Example usage
console.log(canSumRecursive(7, [2, 3])); // true (3 + 2 + 2)
console.log(canSumRecursive(7, [5, 3, 4, 7])); // true (3 + 4 or 7)
console.log(canSumRecursive(7, [2, 4])); // false/**
* Can Sum - Memoization
* Time: O(n * m), Space: O(m)
*/
function canSumMemo(target, nums, memo = {}) {
// Check memo
if (target in memo) return memo[target];
// Base cases
if (target === 0) return true;
if (target < 0) return false;
// Try each number
for (let num of nums) {
if (canSumMemo(target - num, nums, memo)) {
memo[target] = true;
return true;
}
}
memo[target] = false;
return false;
}
// Example usage
console.log(canSumMemo(7, [2, 3])); // true
console.log(canSumMemo(7, [5, 3, 4, 7])); // true
console.log(canSumMemo(300, [7, 14])); // false (fast with memo)/**
* Can Sum - Bottom-Up DP
* Time: O(n * m), Space: O(m)
*/
function canSumBottomUp(target, nums) {
const dp = Array(target + 1).fill(false);
dp[0] = true; // Base case
for (let i = 0; i <= target; i++) {
if (dp[i]) {
for (let num of nums) {
if (i + num <= target) {
dp[i + num] = true;
}
}
}
}
return dp[target];
}
// Example usage
console.log(canSumBottomUp(7, [2, 3])); // true
console.log(canSumBottomUp(7, [5, 3, 4, 7])); // true
console.log(canSumBottomUp(300, [7, 14])); // falseProblem: Given a target sum and an array of numbers, return an array containing any combination that adds up to the target. Return null if no combination exists.
/**
* How Sum - Recursive
* Time: O(n^m * m), Space: O(m)
*/
function howSumRecursive(target, nums) {
// Base cases
if (target === 0) return [];
if (target < 0) return null;
// Try each number
for (let num of nums) {
const remainder = target - num;
const remainderResult = howSumRecursive(remainder, nums);
if (remainderResult !== null) {
return [...remainderResult, num];
}
}
return null;
}
// Example usage
console.log(howSumRecursive(7, [2, 3])); // [3, 2, 2] or [2, 2, 3]
console.log(howSumRecursive(7, [5, 3, 4, 7])); // [4, 3] or [7]
console.log(howSumRecursive(8, [2, 3, 5])); // [2, 2, 2, 2] or [3, 5]/**
* How Sum - Memoization
* Time: O(n * m^2), Space: O(m^2)
*/
function howSumMemo(target, nums, memo = {}) {
// Check memo
if (target in memo) return memo[target];
// Base cases
if (target === 0) return [];
if (target < 0) return null;
// Try each number
for (let num of nums) {
const remainder = target - num;
const remainderResult = howSumMemo(remainder, nums, memo);
if (remainderResult !== null) {
memo[target] = [...remainderResult, num];
return memo[target];
}
}
memo[target] = null;
return null;
}
// Example usage
console.log(howSumMemo(7, [2, 3])); // [3, 2, 2]
console.log(howSumMemo(7, [5, 3, 4, 7])); // [4, 3]
console.log(howSumMemo(300, [7, 14])); // null (fast with memo)/**
* How Sum - Bottom-Up DP
* Time: O(n * m^2), Space: O(m^2)
*/
function howSumBottomUp(target, nums) {
const dp = Array(target + 1).fill(null);
dp[0] = []; // Base case
for (let i = 0; i <= target; i++) {
if (dp[i] !== null) {
for (let num of nums) {
if (i + num <= target) {
dp[i + num] = [...dp[i], num];
}
}
}
}
return dp[target];
}
// Example usage
console.log(howSumBottomUp(7, [2, 3])); // [2, 2, 3]
console.log(howSumBottomUp(7, [5, 3, 4, 7])); // [7]
console.log(howSumBottomUp(8, [2, 3, 5])); // [2, 2, 2, 2]Problem: Given a target sum and an array of numbers, return the shortest combination of numbers that add up to the target. Return null if no combination exists.
/**
* Best Sum - Recursive
* Time: O(n^m * m), Space: O(m^2)
*/
function bestSumRecursive(target, nums) {
// Base cases
if (target === 0) return [];
if (target < 0) return null;
let shortestCombination = null;
// Try each number
for (let num of nums) {
const remainder = target - num;
const remainderCombination = bestSumRecursive(remainder, nums);
if (remainderCombination !== null) {
const combination = [...remainderCombination, num];
// If this is shorter than current best, update
if (shortestCombination === null ||
combination.length < shortestCombination.length) {
shortestCombination = combination;
}
}
}
return shortestCombination;
}
// Example usage
console.log(bestSumRecursive(7, [5, 3, 4, 7])); // [7]
console.log(bestSumRecursive(8, [2, 3, 5])); // [3, 5]
console.log(bestSumRecursive(8, [1, 4, 5])); // [4, 4]/**
* Best Sum - Memoization
* Time: O(n * m^2), Space: O(m^2)
*/
function bestSumMemo(target, nums, memo = {}) {
// Check memo
if (target in memo) return memo[target];
// Base cases
if (target === 0) return [];
if (target < 0) return null;
let shortestCombination = null;
// Try each number
for (let num of nums) {
const remainder = target - num;
const remainderCombination = bestSumMemo(remainder, nums, memo);
if (remainderCombination !== null) {
const combination = [...remainderCombination, num];
// If this is shorter than current best, update
if (shortestCombination === null ||
combination.length < shortestCombination.length) {
shortestCombination = combination;
}
}
}
memo[target] = shortestCombination;
return shortestCombination;
}
// Example usage
console.log(bestSumMemo(7, [5, 3, 4, 7])); // [7]
console.log(bestSumMemo(8, [2, 3, 5])); // [3, 5]
console.log(bestSumMemo(100, [1, 2, 5, 25])); // [25, 25, 25, 25]/**
* Best Sum - Bottom-Up DP
* Time: O(n * m^2), Space: O(m^2)
*/
function bestSumBottomUp(target, nums) {
const dp = Array(target + 1).fill(null);
dp[0] = []; // Base case
for (let i = 0; i <= target; i++) {
if (dp[i] !== null) {
for (let num of nums) {
if (i + num <= target) {
const combination = [...dp[i], num];
// If this is better than current solution, update
if (dp[i + num] === null ||
combination.length < dp[i + num].length) {
dp[i + num] = combination;
}
}
}
}
}
return dp[target];
}
// Example usage
console.log(bestSumBottomUp(7, [5, 3, 4, 7])); // [7]
console.log(bestSumBottomUp(8, [2, 3, 5])); // [5, 3]
console.log(bestSumBottomUp(100, [1, 2, 5, 25])); // [25, 25, 25, 25]| Problem | Approach | Time Complexity | Space Complexity |
|---|---|---|---|
| 0/1 Knapsack | Recursive | O(2^n) | O(n) |
| Memoization | O(n × W) | O(n × W) | |
| Bottom-Up | O(n × W) | O(n × W) | |
| Space Optimized | O(n × W) | O(W) | |
| Unbounded Knapsack | Recursive | O(2^n) | O(W) |
| Memoization | O(n × W) | O(n × W) | |
| Bottom-Up | O(n × W) | O(n × W) | |
| Space Optimized | O(n × W) | O(W) | |
| Subset Sum | Recursive | O(2^n) | O(n) |
| Memoization | O(n × sum) | O(n × sum) | |
| Bottom-Up | O(n × sum) | O(n × sum) | |
| Space Optimized | O(n × sum) | O(sum) | |
| Can Sum | Recursive | O(n^m) | O(m) |
| Memoization | O(n × m) | O(m) | |
| Bottom-Up | O(n × m) | O(m) | |
| How Sum | Recursive | O(n^m × m) | O(m) |
| Memoization | O(n × m²) | O(m²) | |
| Bottom-Up | O(n × m²) | O(m²) | |
| Best Sum | Recursive | O(n^m × m) | O(m²) |
| Memoization | O(n × m²) | O(m²) | |
| Bottom-Up | O(n × m²) | O(m²) |
Where: n = number of items, W = knapsack capacity, sum/m = target sum
- Recursion → Memoization: Adding memoization converts exponential time to polynomial time
- Bottom-Up vs Memoization: Similar complexity, bottom-up avoids recursion overhead
- Space Optimization: Trading space for slightly more complex implementation
- 0/1 vs Unbounded: Key difference is whether items can be reused (affects loop direction in space-optimized version)
- Sum Problems: Complexity depends on both array size (n) and target value (m)
- Recursive: Learning, understanding the problem structure
- Memoization: When you want to preserve recursive structure with better performance
- Bottom-Up: Production code, easier to reason about iteratively
- Space Optimized: Memory-constrained environments, large capacity/sum values