Java program for combination | nCr

 

class NCR {

    // Time Complexity O(n) and Space Complexity O(1)

    int nCr(int n, int r) {

        // Formula n!/(r!*(n-r)!)

        int factorialN = factorial(n);

        int factorialR = factorial(r);

        int factorialNMinusR = factorial(n-r);

        return factorialN / (factorialR * factorialNMinusR);

    }    

    // Time Complexity O(n) and Space Complexity O(n)

    int nCr_pascalTriangle(int n, int r) {

        if(r == 0 || n == r) {

            return 1;

        }

        return nCr_pascalTriangle(n-1, r-1) + nCr_pascalTriangle(n-1, r);

    }

    // Time Complexity O(n) and Space Complexity O(1)

    int factorial(int n) {

        if(n <= 1) { //To return 1st and 2nd term

            return 1;

        }

        int result = 1;

        for(int i = 1; i <= n; i++) {

            result *= i;

        }

        return result;

    }

public static void main (String[] args) {

    NCR obj = new NCR();

    int n = 4, r = 2;

    System.out.println(obj.nCr(n, r));

    System.out.println(obj.nCr_pascalTriangle(n, r));

}

}