N과 M(9)

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

풀이

기존의 n과 m 문제와 비슷하게 풀이할 수 있다.

하지만

문제에서 조건에 중복된 수열은 출력하지 않는다.

라는 조건이 추가되어 약간의 조정이 필요하다.

기존의 풀이에서는 cnt가 m과 같아지면 출력을 했지만 이번에는 출력을 하지않고 문자열로 만들어 배열에 따로 저장을 했다. 이렇게 하면 이전에 만들어진 수열에 대해 중복되었는지 아닌지를 검사할 수 있기 때문이다.

이렇게 모든 경우의 수에 대해 수열을 다 만들고 결과를 출력하면 된다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;
    static int cnt = 0;
    static int[] arr;
    static boolean[] visit;
    static int[] ans;
    static ArrayList<String> ansStr;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        arr = new int[n];
        visit = new boolean[n];
        ans = new int[m];

        String[] line = br.readLine().split(" ");
        for (int i = 0; i < line.length; i++) {
            arr[i] = Integer.parseInt(line[i]);
        }
        Arrays.sort(arr);

        ansStr = new ArrayList<>();

        backTracking(0);

        for(String s : ansStr)
            System.out.println(s);

        bw.close();
        br.close();
    }

    private static void backTracking(int cnt) {
        if (cnt == m) {
            StringBuilder sb = new StringBuilder();
            for (int a : ans) {
                sb.append(a);
                sb.append(" ");
            }
            String t = sb.toString();
            if(!ansStr.contains(t))
                ansStr.add(t);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                ans[cnt] = arr[i];
                backTracking(cnt + 1);
                visit[i] = false;
            }
        }
    }
}