boj 15663 N과 M (9)

www.acmicpc.net/problem/15663

15663번: N과 M (9)

N과M 9번째 문제입니다.

 

다른 문제들과 다른 점은 배열에 중복되는 숫자가 포함되어 주어진다는 것입니다.

 

결과를 출력하였을 때 중복 값을 제외하고 출력해야해서 Set에 ArrayList를 넣어 중복체크를 하였습니다.

 

수열은 오름차순으로 이루어져야한다는 말이 없으니 0번 인덱스부터 계속 돌려주시면 됩니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static ArrayList<Integer> list, ans;
    static int N, M;
    static boolean visit[];
    static Set<ArrayList<Integer>> s = new HashSet<>();
 
    static void dfs(int cnt) {
        if (cnt == M) {
            if (s.contains(ans))
                return;
 
            s.add(ans);
            for (int i = 0; i < ans.size(); i++) {
                sb.append(ans.get(i) + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = 0; i < N; i++) {
            if (visit[i])
                continue;
 
            int x = list.get(i);
 
            visit[i] = true;
            ans.add(x);
            dfs(cnt + 1);
            ans.remove(cnt);
            visit[i] = false;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new ArrayList<>();
        ans = new ArrayList<>();
        visit = new boolean[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }
        Collections.sort(list);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(0);
        System.out.println(sb.toString());
    }
}