[백준][15649번]N과 M(1)[JAVA]

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

풀이 방법

• 전형적인 백트래킹 문제였다.
• 백트레킹의 기초이기 때문에 따로 풀이가 없고, 잘 모르는 사람은 유튜브에 강의를 벡트래킹 찾아보기 바란다.

알아야되는 개념

• 백트래킹

import java.util.Scanner;
 
public class Main {
    private static int N,M;
    private static boolean visit[];
    private static int arr[];
    static void func(int depth, int N, int M){
        if (depth == M){
            for(int i=0;i<M;i++){
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        else {
            for (int i = 1; i <= N; i++) {
                if (visit[i] == true) continue;
                visit[i] = true;
                arr[depth] = i;
                func(depth + 1, N, M);
                visit[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        visit = new boolean[10];
        arr = new int[10];
        func(0, N, M);
    }
}