Class Combinations

java.lang.Object
topics.dynamic.combinations.Combinations
public class Combinations extends Object

Combinations (n choose k)

Calculates the mathematical combinations of n elements taken k at a time. This implementation highlights the dramatic difference between Naive Recursion (Exponential time) and Dynamic Programming (Polynomial time).

The Overlapping Subproblems Trap

The mathematical recurrence relation is:
C(n, k) = C(n-1, k-1) + C(n-1, k)
If implemented using pure recursion, it repeatedly calculates the exact same branches, leading to a catastrophic time complexity of O(2^n).

Dynamic Programming Solution (Pascal's Triangle)

By utilizing a 2D array (memoization table), we compute the values systematically from the bottom up, effectively building Pascal's Triangle. We store the intermediate values, ensuring each subproblem is solved exactly once.

Complexity Analysis (DP Version)

  • Time Complexity: O(N × K) - We fill a 2D matrix of size N*K.
  • Space Complexity: O(N × K) - To store the matrix (can be optimized to O(K) using a 1D rolling array).
Author:
vicegd

  • Constructor Details

    • Combinations

      public Combinations()

  • Method Details

    • combinationsDP

      public long combinationsDP(int n, int k)
      Calculates combinations using Dynamic Programming (Bottom-Up).
      Parameters:
      n - Total number of elements.
      k - Number of elements to choose.
      Returns:
      The number of combinations.

    • combinationsRecursive

      public long combinationsRecursive(int n, int k)
      Calculates combinations using Naive Recursion. WARNING: This method exhibits O(2^n) exponential time complexity. It is included strictly for educational performance comparisons.
      Parameters:
      n - Total number of elements.
      k - Number of elements to choose.
      Returns:
      The number of combinations.