[ 백준 15652 JAVA ] N과 M (4) (Feat. 백트래킹)

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

15652번: N과 M (4)

 

SOLVE

 

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

// 중복을 허용하는 조합 

public class n과m4 {
	static int N, M;
	static int[] result;

	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());
		result = new int[M];

		DFS(0,1);
	}// main end

	public static void DFS(int sidx, int idx) {
		if(sidx==M) {
			for(int a : result) 
				System.out.print(a + " ");
			System.out.println();
			return;
		}
		
		for(int i=idx; i<=N; i++) {
			result[sidx] = i;
			DFS(sidx+1, i); 
		}
	}
}

 

REVIEW

중복을 허용하지 않는 조합에서 약간의 변화를 주면 된다. 

중복을 허용하지 않는 경우 재귀의 For문이 다음과 같이 돌았다면, 

 

// 중복을 허용하지 않는 조합의 경우
for(int i = idx; i<=N;i++) {
			result[sidx] = i;
			NCR(i+1, sidx+1);
		}

 

재귀에서 i+1이 아닌 i를 넣어 중복한 숫자도 결과로 출력가능하도록 만들었다.  

 

// 중복을 허용하는 조합의 경우
for(int i=idx; i<=N; i++) {
			result[sidx] = i;
			DFS(sidx+1, i);
		}