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

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

 

이전 문제와 다른것은 역시 순열이 아니라 조합이라는 것이다.

 

전부터 순열과 조합의 차이점은 visit라는 요소 대신 at이라는 요소를 dfs파라미터에 넣어주어 arr에 들어가는 이전값의 다음 인덱스부터 for을 돌려 자신보다 같거나 작은 값은 넣지 않도록 해주었다.

 

이 문제 또한 같은 방식으로 풀어보았다. 이전 문제에 넣었던 before은 넣어주었다.

 

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 + 1, depth + 1);
//					visit[i] = false;
//				}
			}
		}
	}
}

 

똑같이 잘 풀렸다. 순열과 조합의 차이는 이것으로 둔다고 생각해도 좋을 것 같다.