Binomial Coefficient Problem

Problem Statement

Given two integers n and k, compute the Binomial Coefficient C(n, k), which represents the number of ways to choose k items from n items without regard to order.

Example:

• Input: n = 5, k = 2
• Output: 10 (there are 10 ways to choose 2 items from 5)

Noob-Friendly Explanation

Imagine you have 5 friends and you want to invite exactly 2 of them to a party. How many different pairs can you form? That's C(5,2) = 10. The Binomial Coefficient tells you the number of ways to pick k things from n things, where the order doesn't matter (picking Alice & Bob is the same as picking Bob & Alice).

Approach 1: Brute Force (Recursion)

Intuition

Use the mathematical identity: C(n, k) = C(n-1, k-1) + C(n-1, k). Either we include an element (then choose k-1 from remaining n-1) or we don't (choose k from remaining n-1). Base cases: C(n, 0) = 1 and C(n, n) = 1.

Algorithm

1. If k == 0 or k == n, return 1
2. Otherwise, return C(n-1, k-1) + C(n-1, k)

public class Solution {
    public int binomialCoeff(int n, int k) {
        // Base cases
        if (k == 0 || k == n) return 1;

        return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k);
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - Each call branches into two recursive calls
• Space Complexity: O(n) - Maximum recursion depth is n

Approach 2: Optimal (Bottom-Up DP with 1D Array)

Intuition

Instead of recalculating overlapping subproblems, we use a 1D array. We process row by row (for each n), updating from right to left so we don't overwrite values we still need.

Algorithm

1. Create array dp of size k + 1, set dp[0] = 1
2. For each row i from 1 to n:
   • Traverse j from min(i, k) down to 1
   • dp[j] = dp[j] + dp[j - 1]
3. Answer is dp[k]

public class Solution {
    public int binomialCoeff(int n, int k) {
        int[] dp = new int[k + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            // Traverse right to left to avoid overwriting
            for (int j = Math.min(i, k); j > 0; j--) {
                dp[j] = dp[j] + dp[j - 1];
            }
        }

        return dp[k];
    }
}

Complexity Analysis

• Time Complexity: O(n * k) - Two nested loops
• Space Complexity: O(k) - Only a single 1D array of size k + 1