[백준 JAVA] 15652번: N과 M (4) - 중복 조합

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

 

import java.util.Scanner;

public class Main {

	public static int[] arr;
	public static int n, m;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

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

		arr = new int[m];
		dfs(2, 0);

	}

	public static void dfs(int at, int depth) {
		if (depth == m) {
			for (int val : arr) {
				System.out.print(val + " ");
			}
			System.out.println();
			return;
		}

		for (int i = at - 1; i <= n; i++) {
			
			arr[depth] = i;
			dfs(i + 1, depth + 1);

		}
	}
}

 

중복이 없는 수열에 경우 at 부터 for문을 돌기 시작하는데(이전 배열에 들어간 값의 다음값) 

이문제는 자기 자신부터 for문이 돌아도 되므로 at - 1 부터 for문이 돌게끔 바꿔주고 처음에 dfs(1,0)으로 하면 0부터 실행되므로 dfs(2,0)으로 답을 구해주었다.

 

그냥 재귀하는 dfs에 i + 1말고 i로 재귀할 수 있도록 바꿔주었다. dfs(1, 0) , for문에 at 그대로 이게 더 직관적인것같다.