[백준] 15649 N과 M(1)

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

15649번: N과 M (1)

 

백트래킹 카테고리에 있는 N과 M 문제들이다. 일단 다른 문제는 안 풀어봐서 잘 모르겠지만 이 문제는 그냥 순열을 구하는 문제이다. 순열 조합 역시 문제에서 많이 활용되는 부분이다 보니 한 번 정리할 필요성이 있어보인다.

---

문제 및 입출력

---

예제

---

코드

import java.util.Scanner;

public class Main
{
     // n개의 숫자 중 m개를 뽑는 사전식 순열
     public static void permutation(String value, boolean[] visit, int n, int m, int cnt)
     {
         if(cnt==m)
          {
             System.out.println(value);
             return;
             }

         for(int i=1; i<=n ; i++)
         {
             if(!visit[i-1])
             {
                 visit[i-1] = true;

                // 첫 번째 값을 넣을 때와 그 외의 경우를 나눠서 value 설정
                 if(cnt==0)
                 {
                     permutation(i + "", visit, n, m, cnt+1);
                 }
                 else
                 {
                     permutation(value + " " + i, visit, n, m, cnt+1);
                 }

                 visit[i-1] = false;
             }
         }
     }
     public static void main(String[] args)
     {
         Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();
         int m = sc.nextInt();

         boolean[] visit = new boolean[n];

         permutation("", visit, n, m, 0);
         sc.close();
     }
}