[BackTracking] boj15650 java "N과 M(2)" - 실버3

N과 M (2) 성공

 

 

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

512 MB

25411

19183

13985

74.975%

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

출력

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

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

예제 입력 1 복사

3 1

예제 출력 1 복사

1 2 3

 

package BackTracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

//Combination 조합
public class boj1549_N과M1 {
	static boolean visit[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String temp[] = br.readLine().split(" ");

		int n = Integer.parseInt(temp[0]);
		int m = Integer.parseInt(temp[1]);

		visit = new boolean[n];
		int[] result = new int[m];
		
		for(int i=0;i<n;i++) {
			visit[i] = true;
			result[0] = i+1;
			Combination(n, m, result, 1, i);
			
		}
	}

	public static void Combination(int n, int m, int result[], int count, int start) {
		if (count == m) {
			for (int a = 0; a < m - 1; a++)
				System.out.print(result[a] + " ");
			System.out.println(result[m - 1]);

			return;
		}

		for (int i = start; i < n; i++) {
			if (visit[i] == false) {
				result[count] = i + 1;
				visit[i] = true;
				Combination(n, m, result, count + 1, i);
				visit[i] = false;
			}
		}
	}

}

 

start 인덱스를 매개변수로 전송하여 지나간 작은수는 순환하지 않도록 수정