[백준 JAVA] 15656번: N과 M (7) - 입력 값 중복 순열

https://acmicpc.net/problem/15656

 

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

public class Main {
	public static int n, m;
	public static int[] a;
	public static int[] arr;
//	public static boolean[] visit;
	public static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();

		a = new int[n];
		arr = new int[m];
//		visit = new boolean[n];

		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}

		Arrays.sort(a);

		dfs(0);
		System.out.println(sb);

	}

	public static void dfs(int depth) {
		if (depth == m) {
			for (int val : arr) {
				sb.append(val + " ");
			}
			sb.append('\n');
			return;
		}

		for (int i = 0; i < n; i++) {
//			if(!visit[i]) {
//				visit[i] = true;
			arr[depth] = a[i];

			dfs(depth + 1);
//				visit[i] = false;
//			}
		}
	}
}

4 2 9 8 7 1

1 1

1 7

1 8

1 9

7 1

7 7

7 8

7 9

8 1

8 7

8 8

8 9

9 1

9 7

9 8

9 9

 

중복을 허용하는 입력받은 값으로 만드는 수열이다.

 

 

전에 풀었던 N과 M (6) 문제에서는 at을 통해서 arr[1]값은 이전에 들어온 값의 다음값부터 넣을 수 있도록 하였지만 

 

이 문제는 그냥 다시 처음부터 넣어주면 되므로 visit도 필요없고 at도 필요없이 0부터 n까지 반복해서 재귀해주면 된다.