[재귀함수, 완전탐색] 순열 구하기

🚩 순열 구하기

 

📖 문제 설명 : N 개의 자연수 중 M 개를 뽑는 경우의 수 출력
중복은 제외되므로 한 번 뽑은 수는 뽑을 수 없다. 1,2 수 중 2개를 뽑을 때,
[1,2], [2,1]의 경우만 가능하다.

 

💡 같은 수는 중복해서 뽑으면 안되므로 해당 수에 대한 사용 표시를 체크하는 배열을 사용한다.

 

// 순열 구하기 (DFS)

const permutation = []

function DFS(n, m, i, visited, arr) {
  if (arr.length >= m) {
    console.log(...arr)
    permutation.push(arr)
    return
  }

  for (let j = 0; j < n.length; j++) {
    if (visited[j] === 0) {
      visited[j] = 1
      DFS(n, m, i + 1, visited, [...arr, n[j]])
      visited[j] = 0
    }
  }
}

function solution(n, m) {
  let answer = 0

  // 중복 제거를 위해 방문 체크
  let visited = Array.from({ length: n.length }, () => 0)

  DFS(n, m, 0, visited, [])
  answer = permutation.length
  return answer
}

let n = [3, 6, 9]
console.log(solution(n, 2))

👨‍💻 코드 설명

1. 한 번 뽑은 카드는 두 번째에 뽑을 수 없기 때문에 뽑은 여부를 기록하는 배열을 사용한다. (visited)

2. 재귀 함수인에서 주어진 카드의 수만큼 반복하면서 카드를 순차적으로 뽑는다. (DFS 호출을 한다는 의미)
여기서 뽑기 전에 해당 카드가 이전에 뽑았는지를 파악하고 뽑지 않았을 경우만 뽑는다.
뽑기가 끝난 후, 뽑았다는 표시를 초기화해준다. (3에 대해 [3,6], [3,9]를 뽑았지만, [6,3], [6,9]도 뽑아야 하기 때문에)

3. baseCase에서 M 만큼 일 때 조합을 출력해 준다.

 

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