Java Programs›Numbers›Calculate Combination (nCr)

Calculate Combination (nCr) in Java

intermediate· Numbers · Combinatorics

Problem

A combination — also called a binomial coefficient — counts how many ways r items can be chosen from n items when order doesn't matter, unlike a permutation, where order does matter.

Given n and r, calculate the number of ways to choose r items from n items.

Input

n = 6, r = 2

Output

C(6, 2) = 15

Java Program

Java

public class CombinationFactorial {
    static long factorial(int num) {
        long result = 1;
        for (int i = 2; i <= num; i++) {
            result *= i; // multiply every integer from 2 up to num
        }
        return result;
    }

    public static void main(String[] args) {
        int n = 6, r = 2;
        long result = factorial(n) / (factorial(r) * factorial(n - r)); // direct nCr formula
        System.out.println("C(" + n + ", " + r + ") = " + result);
    }
}

▶ Run Code

Output

C(6, 2) = 15

Core Logic

The textbook formula for a combination — n! divided by r! times (n − r)! — translates directly into code once a factorial helper exists.

How It Works

1factorial(num) multiplies every integer from 2 up to num into a running product.
2factorial(n), factorial(r), and factorial(n - r) are each computed using that helper.
3The final result divides factorial(n) by the product of the other two, exactly matching the nCr formula.
4This is the direct, formula-first way to compute a combination, with no attempt to avoid the intermediate factorial values.

For n = 6, r = 2, factorial(6) = 720, factorial(2) = 2, and factorial(4) = 24, so 720 / (2 × 24) = 15.

💡

Key Point: Computing full factorials like this can overflow a long surprisingly quickly — factorial(21) already exceeds what a 64-bit long can hold, even though the final nCr answer itself might be small.

Complexity

Time Complexity: O(n)Space Complexity: O(1)

Why: Each factorial call is its own loop up to its argument, and computing factorial(n) — the largest of the three — dominates the total work.

Key Concepts

factorialcombinatoricsnCr formula

Approach 2: Pascal's Triangle (Dynamic Programming)

Java

public class CombinationDP {
    public static void main(String[] args) {
        int n = 6, r = 2;
        long[][] dp = new long[n + 1][r + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= Math.min(i, r); j++) {
                if (j == 0 || j == i) {
                    dp[i][j] = 1; // exactly one way to choose nothing or everything
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; // Pascal's identity
                }
            }
        }

        System.out.println("C(" + n + ", " + r + ") = " + dp[n][r]);
    }
}

▶ Run Code

Output

C(6, 2) = 15

Core Logic

Building combinations up from smaller ones — the same additive rule Pascal's triangle uses — avoids ever computing a full factorial, sidestepping the overflow risk entirely.

How It Works

1dp[i][j] holds the value of C(i, j), filled in order of increasing i.
2The edge cases dp[i][0] and dp[i][i] are always 1, since there's exactly one way to choose nothing or everything.
3Every other entry uses Pascal's identity: C(i, j) = C(i - 1, j - 1) + C(i - 1, j).
4By the time the table reaches row n, dp[n][r] holds the answer, built entirely from smaller sums.

For n = 6, r = 2, the table builds up through rows 0 to 6, with dp[6][2] ending at 15 — the same answer the factorial version found.

💡

Key Point: Every value in this table stays small and well within a long's range, since it's built from sums of smaller combinations rather than a single enormous factorial.

Complexity

Time Complexity: O(n × r)Space Complexity: O(n × r)

Why: The table holds one entry per (row, column) pair up to n and r, and filling it requires visiting each of those cells exactly once.

Key Concepts

dynamic programmingPascal's identity2D array

Approach 3: Java 8

Java

import java.util.stream.IntStream;

public class CombinationStream {
    public static void main(String[] args) {
        int n = 6, r = 2;
        // Multiplies by the next numerator and divides by the next denominator in the same step
        long result = IntStream.range(0, r)
            .boxed()
            .reduce(1L, (acc, i) -> acc * (n - i) / (i + 1), (a, b) -> a * b);
        System.out.println("C(" + n + ", " + r + ") = " + result);
    }
}

▶ Run Code

Output

C(6, 2) = 15

Core Logic

The multiplicative nCr formula — multiply and divide one term at a time, staying an integer at every step — can be expressed as a single stream reduction.

How It Works

1IntStream.range(0, r).boxed() generates the offsets 0 through r - 1 as a boxed Stream<Integer>, since the reduction below changes the running type to long.
2.reduce(1L, (acc, i) -> acc * (n - i) / (i + 1), (a, b) -> a * b) folds over the offsets, at each step multiplying by the next numerator term n - i and dividing by the next denominator term i + 1.
3Multiplying before dividing at each step is what keeps every intermediate value an exact integer, the same trick the identity C(n, k) = C(n, k-1) × (n-k+1) / k relies on.
4The third argument to reduce() is a combiner, only used if the stream ran in parallel — here it just mirrors the same multiplication.

For n = 6, r = 2, offset 0 gives 1 × 6 / 1 = 6, and offset 1 gives 6 × 5 / 2 = 15 — the same answer as the other two approaches.

💡

Key Point: This avoids both the factorial version's overflow risk and the DP table's O(n × r) memory, at the cost of being the least obvious of the three to read.

Complexity

Time Complexity: O(r)Space Complexity: O(1)

Why: The stream folds over exactly r offsets with a single running long accumulator, never storing a table or a full factorial.

Key Concepts

Streamboxed()reduce()multiplicative formula

Calculate Permutation (nPr)

Related Programs

Numbersintermediate

Calculate Permutation (nPr)

Numbersintermediate

Calculate Power Using Recursion

Numbersbeginner

Check Abundant Number

Numbersbeginner

Check Armstrong Number

Numbersbeginner

Check Automorphic Number