[Algorithm]조합(Combination)

조합

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

nCr = n-1Cr-1 + n-1Cr

조합은, 하나의 원소를 선택 할 경우 + 하나의 원소를 선택하지 않을 경우 이 둘의 합을 나타낸다.

👉사과가 5개 있고, 각 사과의 번호가 1,2,3,4,5 일 때 3개의 사과 뽑기
3번 사과를 반드시 뽑는 경우 = 4C2 (3번은 정해져 있으므로, 1,2,4,5 중 2개 뽑기)
3번 사과를 뽑지 않는 경우 = 4C3 (3번은 안뽑을거니까, 1,2,4,5 중 3개 뽑기)
두 경우를 합하면 결국 사과를 3개 뽑는 모든 경우의 수 5C3이 됨

---

1. 조합 경우의 수 구하기

nCr

1. 재귀를 통해서 호출을 하다 r==0이 될 경우, r개를 다 뽑은 경우는 더 이상 선택의 여지가 없으므로 1을 리턴
2. 전체 개수 n이 뽑아야 할 개수 r과 같아졌다면 다 뽑는 것 말고 선택의 여지가 없으므로 1을 리턴

public static void main(String[] args){
	System.out.println(combination(3,2)); //3개 중 2개를 뽑는 조합의 경우의 수
}

public static int combination(int n, int r){
	if(n == r || r == 0)
    	return 1;
    else
    	return combination(n-1, r-1) + combination(n-1, r);
}

---

2. 조합 구하기

• 배열의 처음부터 마지막까지 돌며

1. 현재의 인덱스를 선택하는 경우
2. 현재의 인덱스를 선택하지 않는 경우
   : 2가지로 모든 경우를 완전 탐색!

• arr : 조합을 뽑아낼 배열
• r : 조합의 길이 (뽑을 개수)
• visited : 조합에 뽑혔는지를 확인하기 위한 배열

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

2-1. 백트래킹

start : 기준
start를 기준으로 start보다 작으면 뽑을 후보에서 제외, start보다 크면 뽑을 후보