[알고리즘]

NP를 이용한 조합

package boj;

import java.util.Scanner;

public class nextCombination {
	static int N,R;
	static int[] input;
	static int[] P;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		R = sc.nextInt();
		
		input = new int[N];
		P = new int[N];//N크기의 flag 배열, 누가 뽑혔는지 관리한다.
		
		for(int i=0; i<N; i++) {
			input[i] = sc.nextInt();
		}
		
		int cnt = 0;
		while(++cnt<=R) P[N-cnt] = 1;
		
		do {
			for(int i = 0; i<N; i++) {
				if(P[i] == 1) System.out.print(input[i]+" ");
			}
			System.out.println();
		}while(np());
		
	}
	
	
	//NPN, n개중에 r 뽑는 순열은 안된다.
	public static boolean np() {
		
		//STEP 1 : 꼭대기를 찾기 위해 맨 뒤부터!
		int i = N-1;//맨뒤부터 쓴다.
		while(i>0 && P[i-1]>= P[i]) --i; //인접한 두 요소 비교
		
		//더이상 앞자리가 없는 상황 : 현 순열의 상태가 가장 큰 수열(마지막 순열)
		if(i==0) return false;
		
		//STEP 2 : 꺾어지는 곳 교환해야해!
		int j = N-1;
		while(P[i-1] >= P[j]) --j;//교환위치(i-1)와 교환 위치보다 큰수인지 비교한다.
		
		//STEP 3
		swap(i-1,j);
		
		//STEP 4
		int k= N-1;
		while(i<k) {
			swap(i++,k--);
		}
		return true;
	}
	
	private static void swap(int i, int j) {
		int temp = P[i];
		P[i] = P[j];
		P[j] = temp;
	}
}