[백준, BOJ 15665] N과 M (11) (java)

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

메모리: 34,648 KB , 시간: 356 ms

사용 알고리즘: 백트래킹, 자료 구조

728x90

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N, M;
    static List<Integer> list;
    static int[] arr;
    static StringBuilder answer;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 입력 받은 자연수 중복 제거
        Set<Integer> set = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            set.add(Integer.parseInt(st.nextToken()));
        }

        // 중복 제거한 자연수 리스트로 변환 후 정렬
        list = new ArrayList<>(set);
        Collections.sort(list);

        arr = new int[M];
        answer = new StringBuilder();

        // 백트래킹으로 조합 찾기
        backTracking(0);

        System.out.print(answer);
    }

    private static void backTracking(int idx) {

        if(idx == M) {
            for(int a : arr) answer.append(a).append(" ");
            answer.append("\n");
            return;
        }

        for(int i = 0; i < list.size(); i++) {
                arr[idx] = list.get(i);
                backTracking(idx + 1);
        }
    }
}