15652. N과 M (4) (자바, Java)

N과M 시리즈 그 네번째. 1번 문제를 중심으로 차이점을 설명하므로, 안보신 분들은 그것부터 보자.

N과M (1)

15649. N과 M (1) (자바, Java)

3번의 중복가능, 2번의 오름차순을 합해 비내림차순으로 정의했다.

중복가능에서 visit로 체크할 필요없다는 점, 오름차순에서 앞 수를 매개변수로 받아 반복문 시작점에 대입해주면 된다는 점을 종합하면 된다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int n, m;
	static int[] arr;
	static StringBuilder sb = new StringBuilder();

	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[m];
		dfs(0, 0);
		System.out.println(sb);
		
	}
	
	static void dfs(int k, int depth) {
		if (depth == m) {
			for (int i : arr) {
				sb.append(i + " ");
			}
			sb.append("\n");
			return;
		}
		
		for (int i=k; i<n; i++) {
			arr[depth] = i+1;
			dfs(i, depth+1);
		}
	}

}