Java를 사용한 조합 구현

---

https://bcp0109.tistory.com/15

조합

조합이란 N개의 숫자 중에서 r개의 수를 순서 없이 뽑는 경우를 말한다.

배열을 처음부터 마지막까지 돌며
1. 현재 인덱스를 선택하는 경우
2. 현재 인덱스를 선택하지 않는 경우
두 가지를 완전 탐색한다.

변수	설명
arr	조합을 뽑아낼 배열
output	조합에 뽑혔는지 체크하는 배열
n	배열의 길이
r	조합의 길이

순열과 달리 조합은 r을 유지할 필요가 없으므로 숫자를 하나 뽑을때마다 r을 하나씩 줄여준다. r==0 일때가 r개의 숫자를 뽑은 경우이다.

백트래킹 이용 구현

---

start 변수는 기준이다.

start 인덱스를 기준으로 start 보다 작으면 뽑을 후보에서 제외, start 보다 크면 뽑을 후보가 된다.

예를 들어 [1,2,3] 배열이 있고 start가 0부터 시작한다.
함수에 들어오면 먼저 i가 start부터 시작하는 for문에 들어간다.
만약 0 인덱스인 1을 뽑는다면 visited[i]는 true가 되고 뽑지 않는다면 visited[i]는 false이다.

1을 선택한 경우와 선택하지 않은 경우 둘 다 봐야 한다.
하지만 더 이상 1은 고려 대상이 아니기 때문에 다음 for문은 무조건 i+1부터 시작해주어야 한다.