재귀함수 조합 탐색

재귀 함수를 사용한 조합 탐색은 언제 사용될까

n개의 요소에서 발생할수 있는 모든 경우의 수는 어떻게 구할수 있을까?

예를들면 [a,b,c] 에서 [a], [b], [c], [a,b] ... 처럼 완전탐색해야하면 어떻게 해야할까

이는 순열과 비슷하게 재귀를 사용해서 각 단계에서 한 요소를 추가하거나 추가하지 않는 선택을 통해 모든 가능한 조합을 생성하는 조합으로 풀이 할 수 있다.

예제

function combine(arr, s, temp) {
  console.log(temp) // 현재 조합을 출력합니다.

  for (let i = s; i < arr.length; i++) {
    temp.push(arr[i]) // 다음 요소를 temp에 추가합니다.
    combine(arr, i + 1, temp) // 재귀 호출
    temp.pop() // 마지막 요소를 제거하고 다음 요소를 추가하기 위해
  }
}

let array = [1, 2, 3]
combine(array, 0, [])

combine 함수는 세 개의 매개변수를 받는다.
- arr: 조합을 생성할 원본 배열
- s: 현재 조합을 생성하기 위해 고려할 시작 인덱스
- temp: 현재까지 구성된 조합을 저장하는 임시 배열
함수가 호출될 때, s는 0으로 시작해서 배열의 첫번째 요소부터 조합을 만들겠다는 의미이고, temp는 비어 있는 배열로 시작해서 조합을 담을 임시 공간으로 사용된다.
함수 내부에서, console.log(temp);를 통해 현재까지의 조합을 출력한다. 이는 재귀의 각 단계에서 현재 조합을 출력하는 것이에요.
for 루프는 시작 인덱스 s부터 배열 arr의 끝까지 반복한다. 반복하는 동안 현재 요소 arr[i]를 temp 배열에 추가하고(temp.push(arr[i]);), 그 다음 요소를 고려하기 위해 combine 함수를 재귀적으로 호출한다(combine(arr, i + 1, temp);).
재귀 호출이 끝나고 돌아오면, temp.pop();를 통해 마지막에 추가했던 요소를 제거한다. 이것은 '백트래킹(backtracking)'이라고 하며, 이전 상태로 돌아가 다음 조합을 시도할 수 있게 한다.
이 과정을 모든 요소에 대해 반복함으로써, 가능한 모든 조합을 생성하고 출력한다.

위의 코드는 재귀적으로 모든 조합을 생성하고, 각 단계에서 생성된 조합을 출력한다. 배열의 각 요소를 포함시킬지 말지를 결정하는 과정을 통해, 배열의 모든 부분집합을 찾아낼 수 있다.