조합 (Combination)

* 조합 (Combination)

 : 서로 다른 n개에서 r개를 뽑는 것을 n개에서 r개를 택하는 조합이라 하고 이 조합의 수를 nCr로 나타낸다. 

 : 조합은 배열을 생각하지 않으므로(순서X) 선택하여 배열하는 순열의 수를 배열의 수로 나눈 값이라고 생각해도 무방하다.

문제. 

4개의 원소(0~3)에서 2개를 뽑는 모든 경우의 수를 출력하시오. (Java)

풀이.

Combination을 구현하려면 어떻게 해야 할까? 

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

위 식은 아래와 같이 이해할 수 있다.

A,B,C,D,E 5명 중 3명을 뽑는 경우, 5C3

이 경우는 A를 기준으로 나눌 수 있다.

1) A가 이미 정해진 경우

  : A, x, x

  : 나머지 4명중 2명을 뽑아야 함. 4C2

2) A가 제외된 경우

  : x, x, x
  : 나머지 4명중 3명을 뽑아야 함. 4C3

∴ 5C3 = 4C2 + 4C3

아니면, 아래 그림으로 이해를 해도 되겠다.

* 코드

// 조합, Combination // arr : 채워 나갈 array // index : arr의 index // n : n개의 원소 중 // k : 뽑아야할(남아있는) 원소의 개수 // target : arr에 실제로 들어가는 값 static void combination(int[] arr, int index, int n, int k, int target) { if (k == 0) { printCombination(arr, index); } else if (target == n) { return; } else { arr[index] = target; // case#1. index에 target으로 채웠어 (index + 1, k - 1, target + 1) combination(arr, index + 1, n, k - 1, target + 1); // case#2. target이 마음에 안들어서 index 못채웠어 (index, k, target + 1) combination(arr, index, n, k, target + 1); } }

* 설명

n = 4, k = 2

0~3의 숫자 중에서 2개를 골라 보자.

1) arr는 빈 array이다. 0~3의 숫자 중에서 2개를 뽑아 채워야 한다.

2) arr[index]에 target을 증가시키면서 채워 넣을 것이다.

3)

Case#1. 

combination(arr, index + 1, n, k - 1, target + 1);

 - [index]에 target을 채워 넣었다.

 - 다음에는 [index+1]에 채워 넣자.

 - 앞으로 k-1개 더 채워야 한다.

 - target은 사용했으므로 target++을 시켜주자.

Case#2. 

combination(arr, index, n, k, target + 1);

 - [index]를 채우지 않았다. target이 마음에 안들어서.

 - 여전히 [index]에 작업중이다.

 - 앞으로 k개 더 채워야 한다.

 - target은 사용하지 않았지만, 마음에 안드니까 target++을 시켜주자.