문제

재귀를 이용해 n개의 숫자 중 m개의 숫자를 뽑는 조합의 경우의 수를 구한다.

예시

n	m	Output
5	3	10
33	19	818809200

풀이 및 회고

• n 개의 수 중 r 개를 뽑는 경우의 수는 위의 공식을 활용하면 풀 수 있다.
• 예를 들어, 5C3 = 4C2 + 4C3 인 식인데, 식의 뒷변은 n과 r이 같아지거나 r이 0이 되면 1이 된다.
• 추가로, n과 r의 값이 커지면 커질수록 경우의 수가 너무 많이 나와 시간복잡도가 나빠지기 때문에, 이차원 배열을 만들고 각 nCr 식의 값을 배열 안에 넣는다.
• 이를 메모이제이션이라 하는데, 이 방법으로 이미 값이 구해진 뿌리 노드는 굳이 DFS로 파고들어가지 않고 Early return 을 해 시간복잡도를 줄일 수 있다.

코드

const solution = (n, r) => {
	const memo = Array.from(Array(35), () => Array(35).fill(0));
	const DFS = (n, r) => {
		if (memo[n][r] > 0) return memo[n][r];
		if (n === r || r === 0) {
			memo[n][r] = 1;
			return 1;
		} else {
			return (memo[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r));
		}
	};
	return DFS(n, r);
};