조합(Combination)

조합?

조합이란 서로 다른 것들 중 몇 개를 순서 없이 골라낸 것이다.

 

서로 다른 n개 중 순서 없이 r개를 뽑는 조합은 nCr로 표현한다.

---

조합 구현 - 반복문

1, 2, 3, 4중 3개를 순서 없이 택할 수 있는 경우를 따진다. 즉, 4C3을 구해본다.

코드

결과

---

조합 구현 - 재귀

코드

결과

---

전체 코드

import java.util.Arrays;

public class Main {

	static int N = 4;
	static int R = 3;
	
	static int[] input = {1, 2, 3, 4};		// n개 원소 가진 배열
	
	static void combination_for() {
		for(int i = 0; i < 4; i++) {
			for(int j = i+1; j < 4; j++) {
				for(int k = j+1; k < 4; k++) {
					System.out.println(input[i] + " " + input[j] + " " + input[k]);
				}
			}
		}
	}
	
	static int[] numbers = new int[R];	// 순열이 저장될 배열(r만큼)
	// 현재 숫자의 다음숫자부터 넣기 때문에 중복 체크는 필요없다.
	
	static void combination_recursive(int cnt, int start) {
		if(cnt == R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for(int i = start; i < N; i++) {
			numbers[cnt] = input[i];
			combination_recursive(cnt + 1, i + 1);	// 현재 숫자(i)의 다음부터 재귀적으로 호출
		}
	}
	
    public static void main(String[] args) {
    	
    	combination_for();
    	
    	System.out.println();
    	
    	combination_recursive(0, 0);
    }
    
}