[알고리즘/java] 조합을 구하는 코드 공식

콤비네이션을 구하는 코드이다.

 

int[] combi 배열을 만들고,

 

for문으로 순회하면서 combi 배열을 채우고,

 

조합해야할 개수의 수만큼 도달했을 때

 

조합되어지는 수들의 경우를 출력한다.

 

package _08_dfsBfs._009_getCombi;

/**
 *  
입력 
4 2

출력
1 2 
1 3 
1 4 
2 3 
2 4 
3 4 
 */

import java.util.Scanner;

public class Main {
	static int[] combi;
	static int n, m;
	
	public static void dfs(int L, int s) {
		if(L == m) {
			for(int x : combi) System.out.print(x + " ");
			System.out.println();
		} else {
			for (int i = s; i <= n; i++) {
				combi[L] = i;
				dfs(L+1, i+1);
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		combi = new int[m];
		dfs(0, 1);
	}
}

 

 

1부터 6까지의 수 중, 2개를 뽑는 경우는

 

6 2

1 2 
1 3 
1 4 
1 5 
1 6 
2 3 
2 4 
2 5 
2 6 
3 4 
3 5 
3 6 
4 5 
4 6 
5 6 

 

와 같이 결과가 나온다.