[인프런 섹션8] 수들의 조합 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션8] 수들의 조합 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-30

1. K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수

2. DFS 종료조건

• 뽑는 횟수 v >= k 인 경우, return;
• sum % m === 0인 경우, cnt++;

if (v >= k) {
  if (sum % m === 0) cnt++;
  return;
}

3. DFS 로직

• 조합을 구하므로 중복X
• DFS 매개변수 : 뽑은 횟수 v, 이전에 뽑은 arr 원소의 인덱스 u

for (let i=u+1; i<arr.length, i++) {
  sum += arr[i];
  DFS(v+1, i);
  sum -= arr[i];
}

4. DFS 초기값

• DFS(0, -1);
• v : 구슬 뽑은 횟수가 0회
• u : arr에서 뽑은 구슬의 인덱스, 아직 뽑기 전이므로 -1

✍️소스코드

2021-06-30

let k = 3;
let m = 6;
let arr = [2, 4, 5, 8, 12];

let cnt = 0;
let sum = 0;

function DFS(v, u) {
  if (v >= k) {
    if (sum % m === 0) cnt++;
    return;
  }

  for (let i = u + 1; i < arr.length; i++) {
    sum += arr[i];
    DFS(v + 1, i);
    sum -= arr[i];
  }
}

DFS(0, -1);
console.log(cnt);