dfs 뼈대 문제에 중복되는 숫자 조합이 없어야 하는 문제 였다.
ex) 1 7 이 등장한 경우 7 1은 (x)n,m의 범위가 크지 않아
idx == m 인 경우에
chk의 원소들을 이어서 하나의 String으로 만들어
Map의 key로 만든다.
ex) 1 2 3 4 중에 1 3의 key는 truefalsetruefalse가 될것이고
3 1의 key값도 truefalsetruefalse가 되기 때문에 순서 상관없이 같은 key로 만들 수 있다.String key = ""; for(int i=0; i<chk.length; i++){ key+=chk[i]+""; }
만약에 map에 해당 key가 없는 경우에 해당 결과값을 출력하고
map에 key값을 넣어줘 같은 숫자 조합은 출력하지 않도록 한다.if(!chkmap.containsKey(key)){ for (int i = 0; i < m; i++) { System.out.print(list[i] + " "); } System.out.println(""); chkmap.put(key,0); return; }
import java.util.*;
public class Main {
static int n;
static int m;
static int[] arr;
static boolean[] chk;
static int[] list;
static Map<String, Integer> chkmap = new HashMap<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
arr = new int[n];
chk = new boolean[n];
list = new int[m];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
dfs(0);
}
public static void dfs(int idx) {
if (idx == m) {
String key = "";
for(int i=0; i<chk.length; i++){
key+=chk[i]+"";
}
if(!chkmap.containsKey(key)){
for (int i = 0; i < m; i++) {
System.out.print(list[i] + " ");
}
System.out.println("");
chkmap.put(key,0);
return;
}
return;
}
for (int i = 0; i < n; i++) {
if (chk[i]) {
continue;
}
list[idx] = arr[i];
chk[i] = true;
dfs(idx + 1);
chk[i] = false;
}
}
}