조합

조합

• n개의 원소를 가진 임의의 집합에서 순서가 없이 r개를 선택하는 것
• 구현 아이디어
  • 하나의 원소를 선택 vs 하나의 원소를 선택하지 않음
    • 선택하는 경우 : n개의 원소 중에서 1개를 뽑는다고 생각 → r-1개를 뽑는다.
    • 선택하지 않는 경우 : n개의 원소 중에서 1개를 뽑지 않는다고 생각 → r개를 뽑는다.

구현

• 조합의 경우의 수 구하기

public class Combination{

    static int combination(int n, int r){
        if(n==r || r==0)
            return 1;
        return combination(n-1, r-1) + combination(n-1, r);
    }

}

• 조합으로 나온 원소 구하기

static void combination(int[] list, boolean[] visited, int depth, int n, int r){
    if(r==0){
        return;
    }
    if(depth == n) {
        return;
    }
    else{
        //원소로 선택
        visited[depth] = true;
        combination(list, visited, depth+1, n , r-1);

        //원소로 선택 X
        visited[depth] = false;
        combination(list, visited, depth+1, n, r);
    }
}