N과M(9) -오름차순 순열(중복 요소 제거)-

package N과M;

import java.util.*;

public class N과M9 {
	public static boolean visit[];
	public static int arr[];
	public static ArrayList<Integer> num;
	public static int N, M;
	public static StringBuilder sb;
	public static String s2;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = "";
		sb = new StringBuilder(s);
		N = sc.nextInt();
		M = sc.nextInt();
		
		visit = new boolean[N];
		arr = new int[M];
		num = new ArrayList<>();
		
		for (int i = 0; i < N; i++) {
			int n = sc.nextInt();
			num.add(n);
		}
		Collections.sort(num);
		
		permutation(0);
		
		System.out.println(sb);
	}

	public static void permutation(int cnt) {
		if (cnt == M) {
			for (int i = 0; i < arr.length; i++) {
				sb.append(arr[i] + " ");
			}
			sb.append("\n");
			return;
		}

		boolean used[]= new boolean[10001];
		for (int i = 0; i < num.size(); i++) {
				if(!visit[i] && !used[num.get(i)]) {
					used[num.get(i)] = true;
					visit[i] =true;
					arr[cnt] = num.get(i);
					permutation(cnt + 1);
					visit[i] =false;
				}
		}
	}

}

N과 M 문제중 가장 정답률이 적은 문제

주어지는 순열을 중복을 제거하여야 했다.

처음에는 contains를 사용하여 중복을 제거했지만 시간초과가 발생했다.

그래서 boolean used[]= new boolean[10001]; 를 통해 사용한 숫자는 다시 넣어주지 않도록 

처리하였다.