백준) 15649. N과 M(1)(자바)

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

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

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

입출력1

입력 : 3 1
출력 : 1
2
3

입출력2

입력 : 4 2
출력 :
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

• 중복 없이
• N개 중에 M개 뽑기

import java.util.Scanner;

// 중복 없이 순열 구하기
public class Main{
         static int N, M;
         static int[] selected, used;
         static StringBuilder sb = new StringBuilder();

        public static void main(String[] args){
            input();
            recursion(1);
            System.out.println(sb.toString());
        }
        public static void input(){
            Scanner sc = new Scanner(System.in);
            N = sc.nextInt();
            M = sc.nextInt();
            selected = new int[M+1];
            used = new int[N+1];
        }

        public static void recursion(int k) { // 1, 2, 3
            if(k == M+1) {
                for(int i=1; i<=M; i++) {
                    sb.append(selected[i]).append(" ");  
                }
                sb.append("\n");
            } else {
                for(int cand=1; cand<=N; cand++) {
                    // 이미 사용한 숫자라면 넘어감
                    if(used[cand] == 1) continue;

                    // 이미 사용한 숫자가 아니라면 진행
                    selected[k] = cand;
                    used[cand] = 1; // 사용한 숫자인지 체크

                    recursion(k+1);

                    selected[k] = 0;
                    used[cand] = 0; // 다음 진행을 위해 원복 (올라가서 다시 뽑기 위함)
                }
            }
        }

}

참고 : 한 번에 끝내는 코딩테스트 369 Java편 초격차 패키지 Online part3