15650번:N과 M (2) [Java]

이 문제는 백트래킹 알고리즘을 이용하여 풀었다. 

 

백트래킹이란

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.

😀 DFS와 백트래킹

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제

 

[소스코드]

package algorithm15650;

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

public class Main {
	static int n, m;
	static int a[];
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();//수 입력
		m = sc.nextInt();//한줄당 개수 입력
		
		a = new int[m];
		
		go(1,0);

	}
	
	public static void go(int index,int depth) {
		//인덱스가 마지막 위치에 도달하면 수열 출력
		if(depth == m) { 
			for(int val:a) {
				System.out.print(val + " ");
			}
			System.out.println();
			return;
		}
		// 1부터 ~ N개의 수를 선택
		for(int i=index; i<=n; i++) {
			a[depth]=i;
			go(i+1,depth+1);
		}
	}
}

실행결과