Number of Combinations (Memoization)

13 Aug, 2021

Problem

The equation above is solution for number of combinations. But instead of using this formula, write a program that uses the following equation to find the combinatorial number using recursion.

input

The first line contains the natural numbers n (3<=n<=33) and r (0<=r<=n).

5 3

33 19

output

Prints the number of combinations on the first line.

10

818809200

Solution

not optimized

function solution(n, r) {
	let answer = [];

	function DFS(n, r) {
		if (n === r || r === 0) return 1;
		else return DFS(n - 1, r - 1) + DFS(n - 1, r);
	}
	answer = DFS(n, r);
	return answer;
}

optimized

function solution(n, r) {
	let answer = [];
	let dy = Array.from(Array(n + 1), () => Array(r + 1).fill(0)); // row n column r is from the problem condition

	function DFS(n, r) {
		if (dy[n][r] > 0) return dy[n][r];
		if (n === r || r === 0) return 1;
		else return (dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r));
	}

	answer = DFS(n, r);
	return answer;
}