[백준 JAVA] 15666번: N과 M (12) - 중복 입력 값 중복 조합

https://www.acmicpc.net/problem/15666.

 

마찬가지로 조합으로 풀면 된다. 

 

at을 추가하자.

 

마찬가지로 중복된 값을 허용하므로 dfs에 넣을때는 이전에 넣었던 자기 자신 값까지 추가 할 수 있도록 dfs(i, depth + 1)해준다.

 

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, 0);
		System.out.println(sb);

	}

	public static void dfs(int at, int depth) {
		if (depth == m) {
			for (int val : arr) {
				sb.append(val + " ");
			}
			sb.append('\n');
			return;
		}
		int before = 0;
		for (int i = at; i < n; i++) {
//			if (!visit[i]) {
				if (before != a[i]) {
					before = a[i];
//					visit[i] = true;
					arr[depth] = a[i];
					dfs(i, depth + 1);
//					visit[i] = false;
//				}
			}
		}
	}
}

 

마지막으로 푼 N과 M문제 완전탐색에 조금 자신감이 생긴다.