java - Combination

조합(Combination) : 여러 개 가운데에서 몇 개를 순서에 관계없이 한 쌍으로 뽑아내어 모음. 또는 그 짝. 가령 a, b, c 셋 가운데서 두 개씩 뽑아 모은 조합은 ab, bc, ca의 세 가지이다.
-. 네이버 국어사전

요즘 알고리즘 문제를 풀면서 Combination을 사용할 기회가 종종 생긴김에 정리해보기로했다.

---

조합의 경우의 수 구하기

//3개중에서 2개를 뽑는 경우
public class Combination {
	public static int combination(int n, int r) {
		if(n == r || r == 0) 
			return 1; 
		else 
			return combination(n - 1, r - 1) + combination(n - 1, r); 
	}
    
    public static void main(String[] args) {
		System.out.println(combination(3, 2)); 
	}
}

---

재귀함수로 조합 구하기

public class Combination {
    public static void comb(int[] arr, boolean[] visited, int index, int r) {
        if (r == 0) {
            for (int i = 0; i < arr.length; i++) {
                if (visited[i]) {
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
            return;
        }
        if (index == arr.length) {
            return;
        } else {
            visited[index] = true;
            comb(arr, visited, index + 1, r - 1);

            visited[index] = false;
            comb(arr, visited, index + 1, r);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        boolean[] visited = new boolean[arr.length];
        int r = 2;
        comb(arr, visited, 0, r);
    }
}