서로 다른 n개의 원소 중 r개를 순서와 상관없이 선택하는 것을 조합이라 한다. nCr로 그 경우의 수를 나타낸다.

for 중첩으로 조합을 생성한다. 순열은 데이터를 나열한다면, 조합은 데이터의 선택 여부가 중요하다.
그래서 첫 for에서 모든 원소를 후보로 삼을 수 없다.
// 5C3
int n = 5;
// i 는 0 부터 n - 2 까지 반복해야 안쪽 반복문에서 선택할 요소가 남는다.
for (int i = 0; i < n - 2; i++) {
// j 는 i + 1 부터 n - 1 까지
for (int j = i + 1; j < n - 1; j++) {
// k 는 j + 1 부터 n 까지
for (int k = j + 1; k < n; k++) {
// 마지막 순간의 i, j, k 는 n - 2, n - 1, n이 된다.
System.out.printf("%d %d %d%n", i, j, k);
}
}
}
for 중첩 대신 재귀함수를 사용하며, 선택의 여부를 배열로 저장한다.
private void combNumbers(
int n, int r,
// 몇번째 원소를 고르고 있는지
int k,
// 어떤 숫자를 판단하고 있는지
int next,
// 현재 완성한 조합
int[] comb
) {
// k == r: 고를 만큼 원소를 골랐다
if (k == r) {
System.out.println(Arrays.toString(comb));
}
// next == n: 고르기 전 고를 대상이 떨어졌다
else if(next == n) {
return;
}
else {
// comb[k]에 이번에 판단중인 숫자를 우선 할당한다.
comb[k] = next;
// next를 선택하고, k + 1번째 원소를 판단하러 넘어간다.
combNumbers(n, r, k + 1, next + 1, comb);
// next를 선택하지 않고 k번째 원소를 판단하러 넘어간다.
// next를 선택하지 않으면 comb[k]에 할당한 next는 덮어씌워진다.
combNumbers(n, r, k, next + 1, comb);
}
}
<aside> 📌
출처. 테킷_알고리즘 4주차_README
</aside>