[백준] 15666 N과 M (12) - 백트래킹 JAVA

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

15666번: N과 M (12)

코드설명

백트래킹 문제입니다.

 

수열에서 본인도 뽑을 수 있는 상황이므로 visited 배열은 사용하지 않습니다.

하지만, 오름차순으로 정렬되어있기에 idx로 계속해서 index를 가지고 있으면서 이미 지니간 arr의 index는 뽑지 않습니다.

 

또한 HashSet을 활용하여 기존의 뽑았었던 수열은 다시 뽑지 않습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static int[] arr;
	public static int[] answerArr;
	public static boolean[] visited;
	public static StringBuilder sb = new StringBuilder();
	public static HashSet<String> hashset = new HashSet<String>();
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer 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());
    	}
    	Arrays.sort(arr);
    	answerArr = new int[M];
    	visited = new boolean[N];
    	simulate(0,0);
    	System.out.println(sb.toString());
    }
    
    public static void simulate(int idx, int level) {
    	if(level == M) {
    		StringBuilder sb1 = new StringBuilder();
    		for(int a : answerArr) {
    			sb1.append(a).append(" ");
    		}
    		
    		if(hashset.contains(sb1.toString()) == false) {
    			
        		for(int a : answerArr) {
        			sb.append(a).append(" ");
        		}
        		sb.append("\n");
        		hashset.add(sb1.toString());
    		}

    		return ;
    	}
    	
    	for(int i=idx;i<N;i++) {
    		answerArr[level] = arr[i];
    		simulate(i, level + 1);
    	}
    }
}