IF - 조합

문제

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그
램을 작성하세요.


예시

InputOutput
[4,2][[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

풀이 및 회고

  • 순열과 달리, 구슬의 순서도 고려해야 한다. 예를 들어 [1,4]가 뽑혔다면 [4,1] 은 경우의 수에 포함되지 않는다.
  • DFS 를 실행할 때 else 조건에서 for문을 돌 때, i 의 시작점이 DFS를 돌 때마다 1씩 커지도록 해야 한다.
  • 그래야 [1,2], [1,3], [1,4] 까지 순회하고 나온 다음부터 임시 배열의 첫 인덱스를 이미 고려했던 1 이 아닌, 2로 시작할 수 있다.

코드

const solution = (n, m) => {
	const answer = [];
	const temp = [];

	const DFS = (L, S) => {
		if (L === m) answer.push([...temp]);
		else {
			for (let i = S; i <= n; i++) {
				temp[L] = i;
				DFS(L + 1, i + 1);
			}
		}
	};

	DFS(0, 1);
	return answer;
};

좋은 웹페이지 즐겨찾기