[알고리즘/인프런] 수들의 조합

문제 

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

 

풀이

function solution(n, k, arr, m) {
  let answer = 0;
  function DFS(L, s, sum) {
    if (L === k && sum % m === 0) answer += 1;
    else {
      for (let i = s; i < n; i++) {
        DFS(L + 1, i + 1, sum + arr[i]);
      }
    }
  }

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

1~n까지 숫자 가운데 r개를 뽑을 때는 for문을 1~n까지 순회하고 배열에서 r개를 뽑을 때는 인덱스가 필요하므로 0~n-1까지 순회하면 된다.