Computer scienceProgramming languagesJavaCode organizationMethods

Recursion

Theory

K-combination

Report a typo

Let's introduce the term k-combination. It is a subset of k distinct elements of a given set.

Two combinations are called different if one of the combinations contains an element, which is not present in the other combination.

The number of k-combinations of a set of n elements is the number of different such combinations. Let’s write this number as C(n, k).

  1. It is easy to understand that C(n, 0) = 1, as you can select 0 elements from the set of n elements by the only way: namely, by not choosing anything.
  2. Also, it is easy to understand that if k > n, then C(n, k) = 0, as it is impossible, for example, to choose five elements from the three given ones.
  3. The following recurrent formula is used to calculate C(n, k) in the other cases: C(n, k) = C(n – 1, k) + C(n – 1, k – 1).

You need to implement a method, which calculates C(n, k) for the specified n and k. It should use the recurrent formula to calculate C(n, k).

Example:

Let n = 3, i.e. there are three elements (1, 2, 3). Let k = 2.
All the different 2-combination of 3 elements: (1, 2), (1, 3), (2, 3).
There are three different combinations, thus C(3, 2) = 3.

Sample Input 1: 

3 2

Sample Output 1: 

3
Write a program in Java 17
import java.util.Scanner;

public class Main {

public static int comb(int n, int k) {
// write your code here
}

/* Do not change code below */
public static void main(String[] args) {
final Scanner scanner = new Scanner(System.in);
final int n = scanner.nextInt();
final int k = scanner.nextInt();
System.out.println(comb(n, k));
}
}
___

Create a free account to access the full topic