📖 Blog 4: Knapsack Pattern (Subset/Partition DP) 🎒

The Knapsack Pattern is one of the most fundamental DP templates. It helps solve problems where we must decide between including or excluding items to achieve some optimal result (maximize profit, minimize cost, or check feasibility).

Think of it as:
👉 “I have items with certain properties (weight, value, number, etc.) — how do I select some of them to achieve the best outcome under constraints?”

🔹 Core Idea of Knapsack DP

We define a state (usually based on item index and remaining capacity/target).
At each step, we decide:

Include the item (if allowed).
Exclude the item.
- Take the best/valid outcome.

🔹 1. Subset Sum Problem ✅

Problem: Given a set of numbers, check if a subset exists whose sum equals a target.

Code:

public class SubsetSum {
    public static boolean isSubsetSum(int[] nums, int target) {
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][target + 1];

        // Base: sum 0 is always possible
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= n; i++) {
            for (int sum = 1; sum <= target; sum++) {
                if (nums[i - 1] <= sum) {
                    // Include or Exclude
                    dp[i][sum] = dp[i - 1][sum] || dp[i - 1][sum - nums[i - 1]];
                } else {
                    dp[i][sum] = dp[i - 1][sum];
                }
            }
        }
        return dp[n][target];
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 7};
        System.out.println(isSubsetSum(nums, 6)); // true
        System.out.println(isSubsetSum(nums, 5)); // false
    }
}

🔹 2. Partition Equal Subset Sum 🎭

Problem: Can we split the array into two subsets with equal sum?

👉 Trick: Total sum must be even. Then just check if subsetSum(total/2) is possible.

Code:

public class PartitionEqualSubsetSum {
    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % 2 != 0) return false;

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int s = target; s >= num; s--) {
                dp[s] = dp[s] || dp[s - num];
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println(canPartition(nums)); // true
    }
}

🔹 3. 0/1 Knapsack Problem 🎒

Problem: Given items with weight[i] and value[i], maximize total value without exceeding capacity.

Code:

public class Knapsack01 {
    public static int knapSack(int W, int[] wt, int[] val, int n) {
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= W; w++) {
                if (wt[i - 1] <= w) {
                    dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] val = {60, 100, 120};
        int[] wt = {10, 20, 30};
        int W = 50;
        System.out.println(knapSack(W, wt, val, val.length)); // 220
    }
}

🔹 4. Target Sum 🔢

Problem: Assign + or - to each number to reach target sum.

👉 Equivalent to partitioning numbers into two subsets with difference = target.

Code:

public class TargetSum {
    public static int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) sum += num;

        if (target > sum || (target + sum) % 2 != 0) return 0;

        int subsetSum = (target + sum) / 2;
        int[] dp = new int[subsetSum + 1];
        dp[0] = 1;

        for (int num : nums) {
            for (int s = subsetSum; s >= num; s--) {
                dp[s] += dp[s - num];
            }
        }
        return dp[subsetSum];
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 1};
        int target = 3;
        System.out.println(findTargetSumWays(nums, target)); // 5
    }
}

🔹 5. Unbounded Knapsack ♾️

Problem: Items can be taken unlimited times.

Example: Coin Change problems.

Code:

public class UnboundedKnapsack {
    public static int unboundedKnapsack(int W, int[] wt, int[] val, int n) {
        int[] dp = new int[W + 1];

        for (int i = 0; i < n; i++) {
            for (int w = wt[i]; w <= W; w++) {
                dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
            }
        }
        return dp[W];
    }

    public static void main(String[] args) {
        int[] val = {10, 40, 50, 70};
        int[] wt = {1, 3, 4, 5};
        int W = 8;
        System.out.println(unboundedKnapsack(W, wt, val, val.length)); // 110
    }
}

🔹 6. Coin Change Variations 💰

Minimum coins to make target.
Number of ways to make target.

Code (Min Coins):

public class CoinChangeMin {
    public static int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;

        for (int coin : coins) {
            for (int a = coin; a <= amount; a++) {
                dp[a] = Math.min(dp[a], 1 + dp[a - coin]);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(coinChange(coins, amount)); // 3 (5+5+1)
    }
}

Code (Number of Ways):

public class CoinChangeWays {
    public static int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int a = coin; a <= amount; a++) {
                dp[a] += dp[a - coin];
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        System.out.println(change(amount, coins)); // 4
    }
}