[백준/자바] 15652번: N과 M (4)

문제

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

풀이

• 자연수 N과 M
• 1부터 N까지 자연수 중에 M개를 고른 수열
• 같은 수 여러 번 선택 가능
• 오름차순

중복 조합을 구하는 문제

	private static void dfs(int idx, int start) {
		if (idx == m) { // m개를 골랐다면 StringBuilder에 추가
			for (int i : li) sb.append(i).append(" ");
			sb.append("\n");
			return;
		}
		
		for (int i = start; i <= n; i++) {
			li[idx] = i;
			dfs(idx + 1, i); // 자기 자신도 들어가야 하기 때문에 i부터 시작
		}
	}

재귀를 통해 중복 조합을 구해 줍니다.

• 중복된 수도 넣어야 하기 때문에 방문 여부는 신경쓰지 않습니다.
• 자기 자신도 포함해서 수를 넣어줘야 하기 때문에 재귀할 때 +1 하지 않습니다.

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int n, m;
	static int[] li;
	
	private static void dfs(int idx, int start) {
		if (idx == m) {
			for (int i : li) sb.append(i).append(" ");
			sb.append("\n");
			return;
		}
		
		for (int i = start; i <= n; i++) {
			li[idx] = i;
			dfs(idx + 1, i);
		}
	}
	
    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());
    	
    	li = new int[m];
    	
    	dfs(0, 1);
    	System.out.println(sb.toString());
    }
}