if (dep == M)
            {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < arr.Length; i++)
                {
                    sb.Append(arr[i] + " ");
                }
                Console.WriteLine(sb.ToString());
                
                return;
            }

이걸 dep == M 일때마다 하고 있는데, dep == M인 경우가 출력의 한 줄마다 발생하니 Console.WriteLine()을 엄청나게 사용하고 있습니다.

StringBuilder를 매번 초기화하니 사용하는 의미가 딱히 없기도 하고요.

위 코드를 아래처럼 고친 다음,

if (dep == M)
            {              
                for (int i = 0; i < arr.Length; i++)
                {
                    sb.Append(arr[i] + " ");
                }
                sb.AppendLine();
                
                return;
            }

StringBuilder를 static으로 하고, DFS(0) 이후 Console.WriteLine(sb.ToString()); 을 시켜서 그동안 쌓아놓은 문자들을 한번에 출력하니 맞았습니다.

이거 한줄 한줄 표현 할필요없이 그냥 Builder에 쌓아놓고 한번에 일렬로 뿌려주어도 되는 문제인가 보네요.. ㅠㅠ

전 한 라인씩

1111111

1111112

1111113

이런식으로 출력을 해야하는줄 알았네요 

한 라인씩 그런 식으로 출력하는 건 맞습니다.

다만 Console.WriteLine()이 느려서 stringbuilder에 문자열을 저장한 뒤에, 한번에 출력하는 겁니다.