[재귀함수, 완전탐색] 조합 구하기

🚩 조합 구하기

 

📖 문제 설명 : 1부터 N 까지의 자연수 중 M 개를 뽑는 방법의 수 출력(조합)

순열과 비슷하지만 순서가 상관 없기 때문에 [1,4] 뽑혔다면 [4,1]은 뽑는것이 불가능하다.

 

💡 뽑은 조합 중에 가장 마지막 카드의 +1부터 N까지 재귀 함수 이용

 

let combination = []

function recursion(n, r, arr) {
  // 배열 길이가 r 보다 클 때
  if (arr.length > r) {
    return
  }

  // arr 마지막 배열 +1 부터 반복문을 실행해야지 중복값이 안들어감
  // 처음 arr 배열은 undefined이기 때문에 || 1을 통해 1로 초기화
  for (let j = arr[arr.length - 1] + 1 || 1; j <= n; j++) {
    recursion(n, r, [...arr, j])
  }
  if (arr.length === r) {
    console.log(...arr)
    combination.push(arr)
  }
}

function solution(n, r) {
  let answer = 0
  let memoization = Array.from(Array(n + 1), () => Array(r + 1).fill(0))

  recursion(n, r, [])
  answer = combination.length
  return answer
}

console.log(solution(4, 2))
// console.log(solution(33, 19))

👨‍💻 코드 설명

1. 초기에는 1부터 N까지 반복문을 통해 재귀 함수를 호출한다. 호출시 해당 인덱스를 뽑은 조합에 넣어준다.

 

2. 재귀를 통해 받은 배열의 마지막 값 +1 부터 N까지 반복하면서 재귀 함수를 호출한다.

ex) (N=4, R=2) 받은 배열이 [2]일 경우 [2,3], [2,4] 가 되어야 하므로 3~4까지 반복 호출해서 각각 해당 인덱스를 누적 시켜준다.

 

3. 주어진 R의 길이에 부합하면 조합을 출력한다.

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.