조합(Combination) 구현

문제를 풀다가...'조합을 구해야하는데...' 까지만 생각하고 실제로 구현하는데 실패했다.

어떻게 구해야하는지 알아보자..

조합

조합은 고등학교때 수학에서 배웠던 적이 있다.
그 뒤로 문과대학생이 된 뒤로는 쳐다도 본 적이 없다.
아무튼.. 조합은 다음과 같다.

• 순서를 고려하지 않고 선택하는 방법
• nCr = n! / (n-r)! * r! 이라고 생각하면 된다.

그럼 이제 이걸 코드로 구현해본다.

public class combination{
  public static void main(String[] args){
     	int [] arr = {1, 2, 3, 4};
		boolean [] visited = new boolean[arr.length()];
        
       combination(arr, visited, 0, 2);
  }
  
  /**
  * @param arr : 원본 배열
  * @param visited : 조합에 뽑혔는지 체크하기 위한 배열
  * @param start : 시작 인덱스
  * @param cnt : 원하는 조합의 길이
  */
  static void combination(int [] arr, boolean [] visited, int start, int cnt){
  if(cnt == 0){
  	 for(int i = 0; i < arr.length; i++){
     	if(visited[i]) System.out.print(arr[i]);
     }
 	System.out.println();
	return;
  }
 
  
  for(int i = start; i < arr.length; i++){
  	visited[i] = true;
    combination(arr, visited, i+1, cnt-1);
    visited[i] = false;
  }
}

백트래킹을 이용해서 구현한 방법이다. visited라는 배열과, cnt라는 숫자를 통해서 원하는 만큼의 조합이 이루어졌으면 더이상 값을 찾지 않고, 그대로 값을 리턴해줄 수 있도록 하였다.

원하는 길이의 조합값을 찾는 다면, 해당 값에서 visted된 값을 다시 false로 변화시킨 다음, 다시 다음 값에서 새로 조합을 만들어낸다.

---

추가로 Stack으로도 구현해보았다.

import java.util.Stack;

public class combination {
    public static void main(String[] args) {
        String[] arr = {"A", "B", "C", "D"};
        Stack<String> stack = new Stack<>();
        stackCombination(arr, stack, 0, 2);
    }

    public static void stackCombination(String[] arr, Stack<String> stack, int start, int r) {
        if (stack.size() == r) {
            System.out.println(stack);
            return;
        }

        for (int i = start; i < arr.length; i++) {
            stack.push(arr[i]);
            stackCombination(arr, stack, i + 1, r);
            stack.pop();
        }
    }
}

stack에 push 하고, 그 다음 조합을 dfs로 탐색한다. 탐색이 끝난다면, stack에서 해당 값을 pop한다.
결과는 다음과 같이 출력된다.

[A, B]
[A, C]
[A, D]
[B, C]
[B, D]
[C, D]