[종만북] n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘 - 완전탐색(BruteForce) + 재귀함수(Recursive Function) JAVA

출처 : 종만북 6.2 재귀 호출과 완전탐색

코드설명

일반적으로 n개의 원소 중 m개를 고르는 조합 알고리즘을 작성할떄, 재귀를 활용합니다.

 

사실 조합의 경우 충분히 for문으로도 구할 수 있습니다. 하지만, 왜 for문으로 구하지 않고 조합을 활용할까요?

이유는 n개의 원소 중 m개를 선택할경우 for문이 총 m개가 필요하기 떄문입니다.

만약 n개의 원소 중 4개를 선택할경우에는 for문이 반드시 4개가 작성되어야 합니다. 이는, 런타임에 주어진 입력값이 변할떄마다 코드를 새로 작성해주어야 하는데, 컴파일언어인 JAVA는 해당 사항이 불가능하기도하고, 너무 비효율적입니다.

 

 

입력예시 1

6 4
1 2 3 4 5 6

코드

재귀함수를 활용합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	
	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());
		getCombByRecursive(new ArrayList<Integer>(), 0);
	}
	
	public static void getCombByRecursive(ArrayList<Integer> picked, int mIdx) {
		if(picked.size() == M) {
			for(int v : picked) {
				System.out.print(v+" ");
			}
			System.out.println();
		}
		
		for(int i=mIdx;i<N;i++) {
			picked.add(i);
			getCombByRecursive(picked, i + 1);
			picked.remove(picked.size() - 1);
		}
		
	}
	
}

 

for문을 활용하여 n개중 4개를 선택할경우.(불편합니다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	
	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());
		getCombByForIterativeOnlySelect4(N);
	}
	
	public static void getCombByForIterativeOnlySelect4(int N) {
		
		for(int i=0; i<N;i++) {
			for(int j=i+1; j<N;j++) {
				for(int k=j+1; k<N;k++) {
					for(int l=k+1; l<N;l++) {
						System.out.println(" "+i+" "+j+" "+k+" "+l);
					}
				}
			}
		}
		
	}
		
}