[백준/자바] 15655번: N과 M (6)

문제

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

풀이

• N개의 자연수 중에서 M개를 고른 수열
• 오름차순

조합을 구하는 문제

15650번: N과 M (2)는 1부터 N까지 자연수의 조합을 찾는 문제지만, 이 문제는 입력 받은 자연수를 갖고 조합을 만드는 문제입니다.

	private static void dfs(int depth, int start) { // 조합 인덱스, 시작할 nums 인덱스
		if (depth == m) { // m개를 골랐다면 출력
			for (int i : arr) sb.append(i).append(' ');
			sb.append('\n');
			return;
		}
		
		for (int i = start; i < n; i++) {
			arr[depth] = nums[i]; // nums의 i번째 값 arr의 depth번째에 삽입
			dfs(depth + 1, i + 1); // 재귀
		}
	}

로직 자체는 N과 M (2)와 같습니다.

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int n, m;
	static int[] nums, arr;
	
	private static void dfs(int depth, int start) {
		if (depth == m) {
			for (int i : arr) sb.append(i).append(' ');
			sb.append('\n');
			return;
		}
		
		for (int i = start; i < n; i++) {
			arr[depth] = nums[i];
			dfs(depth + 1, i + 1);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		nums = new int[n];
		arr = new int[m];
		for (int i = 0; i < n; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(nums);
		
		dfs(0, 0);
		
		System.out.println(sb.toString());
	}

}