IF - 수들의 조합

문제

N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수
는 몇 개가 있는지 출력하는 프로그램을 작성하세요.
예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을
찾으면 4+8+12 2+4+12로 2가지가 있습니다.

예시

K : 3
numbers : [2, 4, 5, 8, 12]
M : 6

풀이

• 지난 순열 풀이들과 달리 이번에는 조합을 구하는 문제이다.
  
• 순열은 [2, 4, 5, 8, 12] 에서 3개를 뽑아야 할 때 [2, 4, 5] , [2, 5, 4] 가 원소는 같지만 순서가 다르므로 서로 다른 나열로 보지만, 조합은 배열 내 원소들이 같으므로 이 둘을 같은 나열로 본다.

const DFS = (L, S) => {
		if (L === k) {
			const sum = temp.reduce((acc, cur) => acc + cur, 0);
			sum % m === 0 && count++;
		} 

• K 개를 뽑아야 하므로, DFS 의 종료조건은 L === K 이다. L===K 일 때 조합 하나가 나왔다는 뜻이므로, 해당 조합의 원소들의 합이 m 의 배수인지 검사한다.

else {
			for (let i = S; i < numbers.length; i++) {
				temp[L] = numbers[i];
				DFS(L + 1, i + 1);
			}
		}

• DFS 의 인자에 S 가 필요한 이유는, DFS 로 깊이가 깊어질 때마다 for 문을 돌 때 이전 깊이에서 temp 에 넣었던 numbers 의 원소를 또 넣으면 안되기 때문이다.

코드

const solution = (numbers, k, m) => {
	let count = 0;
	const temp = Array.from({ length: k }, () => 0);

	const DFS = (L, S) => {
		if (L === k) {
			const sum = temp.reduce((acc, cur) => acc + cur, 0);
			sum % m === 0 && count++;
		} else {
			for (let i = S; i < numbers.length; i++) {
				temp[L] = numbers[i];
				DFS(L + 1, i + 1);
			}
		}
	};

	DFS(0, 0);
	return count;
};