[코테 매일 풀기 17일차] 1127

백준 15649 N과M(1)

중복 없는 순열

• index를 기준으로 인덱스가 m이 되는 순간 출력한다.
• 선택할 배열에 숫자를 넣으면서 index+1을 담은 변수로 재귀 호출을 한 뒤, boolean 배열을 다시 false로 백트래킹한다.

import java.util.Scanner;

public class Main {
    static boolean[] isSelected;
    static int[] select;
    static int n, m ;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //1부터 n까지 중복없이 m개를 고른 수열
        //n = 3, m = 2
        n = scan.nextInt();
        m = scan.nextInt();
        select = new int[m];
        isSelected = new boolean[n];


        combi(0);//index
    }
    static void combi(int index){
        StringBuilder sb = new StringBuilder();
        if (index>=m){
            //출력
            for (int i = 0; i<m; i++){
                sb.append(select[i]).append(" ");
            }
            System.out.println(sb);
            return;
        }

        for (int i=0; i<n; i++){
            if(!isSelected[i]){
                //select[index]
                select[index] = i+1;
                isSelected[i] = true;
                combi(index+1);
                isSelected[i] = false;
            }
        }


    }
}