Counting Unique Binary Search Trees

A binary search tree requires that all keys in the left subtree are smaller than the root, and all keys in the right subtree are larger. The number of structurally unique BSTs that store n distinct values depends only on n. Let ways[i] be the number of unique BSTs with i nodes. For the root, if the left subtree contains k nodes, the right subtree contains i-1-k nodes. The total configurations contributed by that root are ways[k] * ways[i-1-k]. Summing over all possible left subtreee sizes gives:

public int countUniqueBST(int n) {
    int[] ways = new int[n + 1];
    ways[0] = 1; // empty tree
    for (int total = 1; total <= n; total++) {
        for (int left = 0; left < total; left++) {
            int right = total - 1 - left;
            ways[total] += ways[left] * ways[right];
        }
    }
    return ways[n];
}

0/1 Knapsack

Each item can be taken at most once. Given weights wt[], values val[], and capacity C, the goal is to maximise total value.

2D formulation

dp[i][c] = best value using first i items with capacity c.

dp[i][c] = max( dp[i-1][c], dp[i-1][c - wt[i]] + val[i] )

Initialise row 0 with 0 when c < wt[0], otherwise val[0].

1D rolling array

By iterating capacity backwards, we ensure each item is used once.

public int knapsack01(int[] wt, int[] val, int capacity) {
    int[] best = new int[capacity + 1];
    for (int i = 0; i < wt.length; i++) {
        for (int c = capacity; c >= wt[i]; c--) {
            best[c] = Math.max(best[c], best[c - wt[i]] + val[i]);
        }
    }
    return best[capacity];
}

Partition Equal Subset Sum

Determine whether a given array of positive integers can be partitioned into two subsets with equal sum. This is a 0/1 knapsack where both weight and value equal the number itself, and we check whether we can reach exactly total/2.

Backtracking approach

public boolean canPartitionBacktrack(int[] nums) {
    int total = Arrays.stream(nums).sum();
    if (total % 2 != 0) return false;
    return tryPartition(nums, 0, total / 2);
}

private boolean tryPartition(int[] nums, int idx, int remaining) {
    if (remaining == 0) return true;
    if (remaining < 0 || idx == nums.length) return false;
    // include current element
    if (tryPartition(nums, idx + 1, remaining - nums[idx])) return true;
    // skip current element
    return tryPartition(nums, idx + 1, remaining);
}

DP approach

We can use a 1D boolean array. reach[s] indicates whether sum s is achievable.

public boolean canPartitionDP(int[] nums) {
    int sum = Arrays.stream(nums).sum();
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    boolean[] reach = new boolean[target + 1];
    reach[0] = true;
    for (int num : nums) {
        for (int s = target; s >= num; s--) {
            reach[s] = reach[s] || reach[s - num];
        }
    }
    return reach[target];
}

Last Stone Weight II

We have a set of stones, and we repeatedly smash two stones together; the smaller one is destroyed and the larger one’s weight reduces by the smaller one. The problem minimises the final possible weight. Its equivalent to splitting the stones into two groups whose sums are as close as possible. Let S/2 be the target capacity; we find the maximum weight achievable without exceeding it.

public int lastStoneWeightII(int[] stones) {
    int total = Arrays.stream(stones).sum();
    int capacity = total / 2;
    int[] maxWeight = new int[capacity + 1];
    for (int stone : stones) {
        for (int c = capacity; c >= stone; c--) {
            maxWeight[c] = Math.max(maxWeight[c], maxWeight[c - stone] + stone);
        }
    }
    return total - 2 * maxWeight[capacity];
}

Target Sum

Given an array nums and a target target, we can assign + or - to each number. We must count the number of ways to achieve the target. Let P be the sum of numbers with + and N the sum of numbers with -. Then P - N = target and P + N = total. Hence P = (total + target) / 2. The problem reduces to counting subsets with sum P.

Backtracking (exponential)

class Solution {
    int count = 0;
    public int findWays(int[] nums, int target) {
        backtrack(nums, 0, 0, target);
        return count;
    }
    private void backtrack(int[] nums, int idx, int currentSum, int target) {
        if (idx == nums.length) {
            if (currentSum == target) count++;
            return;
        }
        backtrack(nums, idx + 1, currentSum + nums[idx], target);
        backtrack(nums, idx + 1, currentSum - nums[idx], target);
    }
}

DP counting subsets

ways[c] = number of subsets that sum to c.

public int findTargetSumWays(int[] nums, int target) {
    int total = Arrays.stream(nums).sum();
    if (Math.abs(target) > total || (total + target) % 2 != 0) return 0;
    int subsetSum = (total + target) / 2;
    int[] ways = new int[subsetSum + 1];
    ways[0] = 1;
    for (int num : nums) {
        for (int s = subsetSum; s >= num; s--) {
            ways[s] += ways[s - num];
        }
    }
    return ways[subsetSum];
}

Ones and Zeroes

Given an array of binary strings, find the maximum number of strings you can select such that the total count of 0s does not exceed m and the total count of 1s does not exceed n. This is a 2‑D 0/1 knapsack.

public int findMaxForm(String[] strs, int m, int n) {
    int[][] best = new int[m + 1][n + 1];
    for (String s : strs) {
        int zeros = (int) s.chars().filter(ch -> ch == '0').count();
        int ones = s.length() - zeros;
        for (int i = m; i >= zeros; i--) {
            for (int j = n; j >= ones; j--) {
                best[i][j] = Math.max(best[i][j], best[i - zeros][j - ones] + 1);
            }
        }
    }
    return best[m][n];
}

Unbounded Knapsack (Complete Knapsack)

Items can be used infinitely many times. The inner capacity loop runs forwards.

Coin Change (Minimum Coins)

Given an amount and coin denominations, find the fewest number of coins that make up that amount. If impossible, return -1.

public int minCoins(int[] coins, int amount) {
    int max = amount + 1;
    int[] minCnt = new int[amount + 1];
    Arrays.fill(minCnt, max);
    minCnt[0] = 0;
    for (int coin : coins) {
        for (int a = coin; a <= amount; a++) {
            minCnt[a] = Math.min(minCnt[a], minCnt[a - coin] + 1);
        }
    }
    return minCnt[amount] > amount ? -1 : minCnt[amount];
}

Coin Change II (Number of Combinations)

Count the number of ways to make amount using unlimited coins. The order of coins does not matter (combinations). We loop items first, then capacity.

public int combinationCount(int amount, int[] coins) {
    int[] ways = new int[amount + 1];
    ways[0] = 1;
    for (int coin : coins) {
        for (int a = coin; a <= amount; a++) {
            ways[a] += ways[a - coin];
        }
    }
    return ways[amount];
}

Combination Sum IV (Number of Permutations)

Count the number of sequences (order matters) that sum to target. Loop capacity first, then items.

public int permutationCount(int[] nums, int target) {
    int[] ways = new int[target + 1];
    ways[0] = 1;
    for (int t = 0; t <= target; t++) {
        for (int num : nums) {
            if (t >= num) {
                ways[t] += ways[t - num];
            }
        }
    }
    return ways[target];
}

Rule: outer loop over capacity yields permutations; outer loop over items yields combinations.

Perfect Squares

Given an integer n, find the least number of perfect square numbers that sum to n. This is an unbounded knapsack where the items are squares i*i with value 1 (each square counts as one coin), and we minimise the count.

public int numSquares(int n) {
    int[] minCnt = new int[n + 1];
    Arrays.fill(minCnt, n + 1);
    minCnt[0] = 0;
    for (int i = 1; i * i <= n; i++) {
        int square = i * i;
        for (int j = square; j <= n; j++) {
            minCnt[j] = Math.min(minCnt[j], minCnt[j - square] + 1);
        }
    }
    return minCnt[n];
}

Word Break

Determine whether a string s can be segmented into a space‑separated sequence of one or more dictionary words. This is a permutation‑like DP where dp[i] indicates whether the prefix of length i can be segmented. We loop over positions first, then over words.

public boolean wordBreak(String s, List<String> wordDict) {
    int n = s.length();
    boolean[] canBreak = new boolean[n + 1];
    canBreak[0] = true;
    for (int end = 1; end <= n; end++) {
        for (String word : wordDict) {
            int len = word.length();
            if (end >= len && canBreak[end - len] 
                && s.substring(end - len, end).equals(word)) {
                canBreak[end] = true;
                break;
            }
        }
    }
    return canBreak[n];
}

House Robber

A thief cannot rob two adjacent houses. Given the amounts in each house, find the maximum loot.

public int robLinear(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    int[] gain = new int[n];
    gain[0] = nums[0];
    gain[1] = Math.max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        gain[i] = Math.max(gain[i - 1], gain[i - 2] + nums[i]);
    }
    return gain[n - 1];
}

House Robber II (Circular)

Houses are arranged in a circle. We break the circle by considering two linear scenarios: excluding the first house, and excluding the last house. The answer is the maximum of the two.

public int robCircular(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}

private int robRange(int[] nums, int start, int end) {
    int size = end - start + 1;
    if (size == 1) return nums[start];
    int[] gain = new int[size];
    gain[0] = nums[start];
    gain[1] = Math.max(nums[start], nums[start + 1]);
    for (int i = 2; i < size; i++) {
        gain[i] = Math.max(gain[i - 1], gain[i - 2] + nums[start + i]);
    }
    return gain[size - 1];
}