조합(Combination) : 여러 개 가운데에서 몇 개를 순서에 관계없이 한 쌍으로 뽑아내어 모음. 또는 그 짝. 가령 a, b, c 셋 가운데서 두 개씩 뽑아 모은 조합은 ab, bc, ca의 세 가지이다.
-. 네이버 국어사전
요즘 알고리즘 문제를 풀면서 Combination을 사용할 기회가 종종 생긴김에 정리해보기로했다.
조합의 경우의 수 구하기
//3개중에서 2개를 뽑는 경우
public class Combination {
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);
}
public static void main(String[] args) {
System.out.println(combination(3, 2));
}
}
재귀함수로 조합 구하기
public class Combination {
public static void comb(int[] arr, boolean[] visited, int index, int r) {
if (r == 0) {
for (int i = 0; i < arr.length; i++) {
if (visited[i]) {
System.out.print(arr[i] + " ");
}
}
System.out.println();
return;
}
if (index == arr.length) {
return;
} else {
visited[index] = true;
comb(arr, visited, index + 1, r - 1);
visited[index] = false;
comb(arr, visited, index + 1, r);
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3};
boolean[] visited = new boolean[arr.length];
int r = 2;
comb(arr, visited, 0, r);
}
}