백준 C# - 15652 +) 풀이

N과 M(4)번 문제이다.

앞서 N과 M(2)번 문제와 비슷한 문제이다.

하지만 2번과 달리 4번에서는 같은 숫자를 골라도 된다.

---

N과 M(2)번 알고리즘 살펴보기

if (!visited[i])
{
    visited[i] = true;
    arr[depth] = i;
    Dfs(i, depth+1);
    visited[i] = false;
}

---

N과 M(4) 알고리즘

자릿수에 같은 숫자가 연속으로 오지 않게하기 위해 visited를 사용하였는데 여기에서 방문부분이 필요 없으므로 이와 관련된 부분을 삭제하면 된다.

arr[depth] = i;
Dfs(i,depth + 1);

---

코드 전문

using System;
using System.Text;

namespace baek2
{
    class Program
    {
        static int N, M = 0;
        static StringBuilder sb = new StringBuilder();
        static int[] arr = new int[9];
        
        public static void Dfs(int at, int depth)
        {
            if(depth == M)
            {
                
                for (int i = 0; i<M;i++)
                {
                    sb.Append(arr[i]).Append(' ');
                }
                sb.AppendLine();
                return;
            }   
            for(int i = at;i<=N;i++)
            {
                arr[depth] = i;
                Dfs(i, depth+1);
            }
        }
        public static void Main()
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            N = input[0];
            M = input[1];

            Dfs(1,0);
            Console.WriteLine(sb.ToString());

        }
    }
}