[인프런 섹션8] 조합 구하기 (Javascript)

👩🏻‍💻문제링크

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

✍️Idea Sketch

2021-06-30

1. M개를 뽑는 방법의 수를 구하기

2. DFS 종료조건

• DFS 매개변수 v : 구슬 뽑은 횟수
• v >= m 이면 return

3. DFS 내부로직

• let res = []
• v는 뽑는 횟수 이므로 뽑는 숫자는 for 반복문 사용
• [3, 4], [4, 3] 같이 중복x
• 이전에 뽑은 숫자정보 필요 --> DFS 두번째 매개변수 u

for (let i = u + 1; i <= n; i++) {
  res.push(i);
  DFS(v + 1, i);
  res.pop();
}

✍️소스코드

2021-06-30

let res = [];
let n = 4, m = 2;
let cnt = 0;

function DFS(v, u) {
  if (v >= m) {
    console.log(res.join(' '));
    cnt++;
    return;
  }

  for (let i = u + 1; i <= n; i++) {
    res.push(i);
    DFS(v + 1, i);
    res.pop();
  }
}

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