백준 C# - 15664 +) 풀이

이 문제를 풀기 앞서 아래 문제를 풀고 오는 것을 추천한다.

백준 C# - 15650 +)풀이

---

N과 M(2)문제와 다른 점 - 중복되는 수열이 여러 번 출력되지 않아야 한다.

그래서 어떻게 풀어야할까 하다가 HashSet을 생각해냈다. HashSet의 가장 큰 특징은 중복을 사용하지 않는 것이다, 그러므로  수열을 저장할때 HashSet을 사용하였다.

if(depth == M)
{
    for(int i = 0; i < M; i++)
    {
        sb.Append(answer[i]).Append(' ');
    }
    answerSet.Add(sb.ToString()); // 이미 존재한다면 Add되지 않는다
    sb.Clear();
    return;
}

---

HashSet 알아보러가기

C# - Set과 HashSet(Add,Remove,Contains,IntersectWith,UnionWith)

---

코드 전문

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace baek2
{
    class Program
    {
        static int N, M;
        static bool[] visited = new bool[9];
        static int[] array = new int[10001];
        static int[] answer = new int[10001];
        static HashSet<string> answerSet = new HashSet<string>();
        static StringBuilder sb = new StringBuilder();
        public static void dfs(int at, int depth)
        {
            if(depth == M)
            {
                for(int i = 0; i < M; i++)
                {
                    sb.Append(answer[i]).Append(' ');
                }
                answerSet.Add(sb.ToString());
                sb.Clear();
                return;
            }

            for(int i = at; i <= N; i++)
            {
                if (!visited[i])
                {
                    visited[i] = true;
                    answer[depth] = array[i - 1];
                    dfs(i,depth + 1);
                    visited[i] = false;
                }
            }
        }
        public static void Main()
        {
            string[] token = Console.ReadLine().Split();
            N = int.Parse(token[0]);
            M = int.Parse(token[1]);
            array = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            Array.Sort(array);
            dfs(1,0);

            foreach (var x in answerSet)
            {
                Console.WriteLine(x);
            }
        }
    }
}