[백준/Java] 15665: N과 M (11)

문제: https://www.acmicpc.net/problem/15665

 

 

조건

• TimeLimit = 1s
• N개중 M개를 고른 수열 (1<=M<=N<=7)
• 수열 내에서는 중복 가능하지만, 수열 자체는 중복되면 안됨
• 가능한 모든 수열을 오름차순으로 출력하라

 

풀이

• 백트래킹
  • 전체 수열만 중복 안되면 되므로, 지역변수 pre를 사용해주자

 

코드

import java.io.*;
import java.util.*;


public class Main {

	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int n;
	static int m;
	static int[] arr;
	static int[] cur;
	
	public static void main(String[] args) throws IOException {

		// input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		arr = new int[n];
		for (int i=0; i<n; i++) arr[i] = Integer.parseInt(st.nextToken());		
		
		// dfs
		Arrays.sort(arr);
		cur = new int[m+1];
		dfs(0);
		
		// result
		System.out.print(sb);
	}
	
	
	
	static void dfs(int size) {
		
		if (size == m) {
			for (int i=0; i<m; i++) sb.append(cur[i]).append(" ");
			sb.append("\n");
			return;
		}
		
		int pre = -1;
		for (int i=0; i<n; i++) {
			
			if (arr[i] == pre) continue;
			pre = arr[i];
			
			cur[size] = arr[i];
			dfs(size+1);
			
		}
	}
	
	
}