문제

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

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

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

입력으로 N과 M이 주어졌을 때 1부터 N까지의 수 중 M개를 뽑아서 수열을 만들어 출력하면 되는 문제이다. 다만 중복 없이 수를 뽑아야 된다는 점을 유의해야한다.

예를들어 N = 3, M = 2 라고 주어졌을 때 첫번째 자리에 1~3 3개가 올수 있고 두번째 자리에는 첫번째 자리에 온 수를 제외한 2개의 수가 올 수 있다.

그러면 앞에서 사용한 수를 제외하려면 boolean 변수를 이용하여 사용 여부를 확인해야하며, 결과를 저장할 배열 역시 필요하다. 문제에서 N과 M의 최대가 8이기 때문에 boolean 배열과 결과를 저장하는 배열의 크기를 10으로 미리 정해두었다.

이제 백트래킹을 해야하는데 함수는 재귀적으로 호출하면 된다. for문을 1부터 N까지 돌리면서 이미 사용한 수(visited[i] == true)라면 건너뛰고 사용하지 않는 수일 때 결과 배열에 해당 수를 넣는다. 넣은 후 함수를 호출하는데 이때 index + 1를 해준다. 그 이유는 결과 배열에 다음번째에 수를 넣기 위함이다.

함수를 호출한 뒤에는 다시 해당 수를 false로 해줘야 한다. 왜냐하면 그 다음 경우에는 사용해야하기 때문이다.

이제 index == m 일때 출력해야하는데 그때는 M까지 for문을 돌려서 결과 배열에 있는 수를 출력해주면 된다.

소스

import java.util.*;

public class Main {
	public static boolean[] visited = new boolean[10];
	public static int[] a = new int[10];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int m = sc.nextInt();

		backtracking(0, n, m);

	}

	public static void backtracking(int index, int n, int m) {
		if (index == m) {
			for (int i = 0; i < m; i++) {
				System.out.print(a[i]);
				if (i != m - 1) {
					System.out.print(" ");
				}
			}
			System.out.println();
			return;
		}

		for (int i = 1; i <= n; i++) {
			if (visited[i])
				continue;

			visited[i] = true;
			a[index] = i;
			backtracking(index + 1, n, m);
			visited[i] = false;
		}
	}
}