[백준] 15656번 : N과 M (7)

문제

 

 

접근 방식

주어진 배열을 정렬하여 중복해서 선택할 때

M개의 수를 고르는 모든 경우를 출력하면 된다.

 

모든 수를 중복해서 계속 사용할 수 있기 때문에

사용 여부를 체크하거나 인덱스에 변화를 줄 필요 없이

계속해서 재귀호출과 M번의 반복문을 돌아주면 된다.

 

풀이

public class Main {

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

	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];
		sequence = new int[m];

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

		Arrays.sort(arr);

		createSequence(0);

		System.out.println(sb);
	}

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

			sb.append("\n");

			return;
		}

		for (int i = 0; i < arr.length; i++) {
			sequence[size] = arr[i];
			createSequence(size + 1);
		}
	}
}