[백준/15650][Java] N과 M(2)

문제

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

15650번: N과 M (2)

설명

N과 M(1)이 백트래킹을 이용한 순열 문제라면 N과 M(2)는 백트래킹을 이용한 조합 문제이다.

조합은 순서가 상관없다. 또한 오름차순으로 구하게되면 이전에 했던 문제와 달리 중복 체크가 필요 없다.

처음에 combination(0,1)을 호출하는데, 이후에는 combination(cnt+1, i+1)을 호출한다.
오름차순으로 구하면 중복체크 하지 않아도 되므로, visited 배열을 따로 사용하지 않았다.
cnt+1은 다음 자릿수 결정한다는 의미이고, i+1은 오름차순이므로 앞자리 숫자보다 무조건 커야함을 의미한다.

코드

package algo0314;

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

public class B15650_N과M2 {
    private static int n, m;
    private static int[] arr; // 원소를 저장할 배열
    private static boolean[] visited; // 중복을 제거하기 위한 방문 처리
    static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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];
		combination(0,1); //글자 몇개 선택, 시작숫자 번호
		System.out.println(sb);
	}
	private static void combination(int cnt, int start) {
		// TODO Auto-generated method stub
		if(cnt == m) { //m개를 다 골랐으면
			for(int i=0;i<m;i++) {
				sb.append(arr[i]).append(" ");
			}
			sb.append("\n");
			return;
		}
		else {
			for(int i=start;i<=n;i++) {
				arr[cnt] = i;//cnt번째에 i 저장. i는 start부터 n까지 들어감
				combination(cnt+1, i+1);//오름차순으로 구하면 중복체크 하지 않아도 됨
				//cnt+1은 다음 자릿수 결정한다는 의미
				//i+1은 오름차순이므로 앞자리 숫자보다 무조건 1이상 커야함을 의미
			}
		}
	}

}