👨‍💻 사건

nCr 과 같은 조합을 기존의 공식을 사용하지않고 구현하는 문제를 접하였다. 처음에는 감이 잡히지않아 먼저 nCr = (n-1)C(r-1) + (n-1)C(r) 이 되는 이유부터 살펴보면서 DFS 를 구현하였다.

✅ 해결

$nCr$ 의 예시로 $5C3$ 이라고 생각할때, 1~5 까지의 숫자에서 3가지를 뽑아서 생기는 경우의 수를 이야기한다.

만약 5를 기준으로 할때는, 자신을 포함해서 3가지를 뽑는경우의 수와 자신을 제외한 경우의 수를 합한 경우와 같다.

이때, 자신을 포함한 경우의 수를 생각하면 자신은 fix 로 박혀있고 나머지 수들(1~4) 중 2가지를 뽑는 경우의 수와 같다.

자신을 제외한 경우의 수를 생각하면 나머지수들(1~4) 에서 3가지의 경우의 수를 뽑는 수와같다.

이를 더하면 $5C3$ 의 값과 동일하다.

이제 위를 토대로 코드를 작성해보면,

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

위와 같다.