[Java] 조합

조합 : 서로다른 N개의 원소에서 R개를 중복없이 순서에 상관없게 선택하는 것 ([1,2] 와 [2,1]은 같다)

 

[입력]

4 2

1 2 3 4

 

[출력]

[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

 

[변수]

- N, R : 존재하는 원소의 수, 뽑을 원소의 갯수

- input : 존재하는 원소들을 담고있는 배열

- numbers : 뽑은 원소들을 담고있는 배열

- cnt : 뽑은갯수를 파악하기 위한 인자값

- start : 현재 뽑은수의 다음 수 부터 뽑기 위해 전달하는 인자값 

 

조합은 순열과 달리 순서에 상관이 없으므로, 다음 수는 현재 뽑은값의 다음 수로 제한하면 중복을 방지할 수 있다. 

 

 

 

import java.util.Arrays;
import java.util.Scanner;

public class Combination {
	static int N,R;
	static int[] input,numbers; //input : 입력수배열, numbers:선택수배열
	
	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);
		N= sc.nextInt();
		R= sc.nextInt();
		
		input= new int [N];
		numbers= new int [R];
		
		for(int i=0;i<N;i++) {
			input[i]=sc.nextInt();
		}
		combination(0,0);
	}
	
	public static void combination(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(cnt+1, i+1);	//다음자리는 현재 뽑은 i의 다음수부터 시작하도록 전달
		}
	}
}