[알고리즘] 조합 nCr 예제

ex)오름차순으로 정렬된,  중복이 없는 정수열로부터, 크기가 3인 모든 부분집합을 출력하는 프로그램을 작성하시오. 부분집합들은 사전 오름차순으로 출력되어야 합니다. 세 숫자 중 첫 숫자가 가장 작은 부분집합이 먼저 출력되어야 하고, 첫 숫자가 같은 두 부분집합 중에는 두 번째 숫자가 더 작은 부분집합이 먼저 출력되어야 합니다.

<입력>

오름차순으로 정렬된, 중복이 없는, 정수열 한 줄

<출력>

크기가 3인 모든 부분집합들을 한 줄에 하나씩 출력한다.

import java.util.Arrays;
import java.util.Scanner;
class Main {

	public static void main(String[] args) {
		int n = 3;
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		String a[] = str.split(" ");
		int[] ans = new int[a.length];
		for(int i=0; i<a.length; i++) {
			ans[i] = Integer.parseInt(a[i]);
		}
		combination(ans,3);
	}
	public static void combination(int[] arr, int destNum) {
		int[] temp = new int[destNum];
		combination(arr,0,destNum,temp);
	}

	public static void combination(int[] arr, int curLoc, int destNum, int[] temp) {
		if(0==destNum) {
			for(int i = 0; i < temp.length; i++) {
				if(i==temp.length-1)
					System.out.print(arr[temp[i]]);
				else
				System.out.print(arr[temp[i]] + " ");
			}
			System.out.println();
			return;
		}
		for(int i = curLoc; i < arr.length; i++) {

			temp[temp.length-destNum] = i;

			combination(arr,i+1,destNum-1, temp);
		}
	}

}