[백준] 15655번 : N과 M (6)

문제

 

 

접근 방식

N과 M 시리즈 2번 문제와 같은 문제로

추가로 주어진 배열 입력에 대해 정렬하여 오름차순으로

수열을 만들어 출력하는 문제다.

 

이전에 등장한 수열이라면 순서 상관없이 중복으로 취급하여

다시 출력하는 경우가 없어야 한다.

 

예를 들어 1 7 8을 출력했으면 8 7 1 같은걸 출력할 필요가 없다.

 

즉, 주어진 배열을 순회하며 수열을 만들 때,

다음 자리 수를 뽑는 재귀 호출 시 시작 인덱스를 1씩 증가시켜주면 된다.

 

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();
	private static int n;
	private static int m;
	private static int[] arr;
	private static int[] permutation;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine(), " ");

		arr = new int[n];
		permutation = new int[m];

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		createSequence(0, 0);

		System.out.println(sb);
	}

	private static void createSequence(int size, int start) {
		if (size == m) {
			for (int i = 0; i < m; i++) {
				sb.append(permutation[i]).append(" ");
			}

			sb.append("\n");

			return;
		}

		for (int i = start; i < arr.length; i++) {
			permutation[size] = arr[i];
			createSequence(size + 1, i + 1);
		}
	}
}