조합

조합

• 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합이라고 부른다.
  nCr = nCn-r
  nCr = n!/(n-r)!*r!
  nCr = n-1Cr-1 + n-1Cr

중복 조합

• 서로 다른 n개의 원소 중에서 중복을 허락하여 r개를 순서 없이 골라낸 것을 중복 조합이라고 부른다.
  nHr = n+r-1Cr

반복문 조합

• for문을 통해 순열을 구할때 문제점
• 원소수 N은 가변이지만 선택한 R개는 고정이 됨
• 재귀호출을 통해 R개를 가변적으로 선택할 수 있다.
• 순서X, 중복 X

for(int i = 0; i < N; ++i){				// 첫번째 원소
	for(int j = i + 1; j < N; ++j){		// 두번째 원소
    	for(int k = j + 1; k < N; ++k){	// 세번째 원소
        	
        }
    }
}

재귀 조합

• 순서X, 중복 X

static void combination(int depth, int start){
	// r개의 원소를 뽑은 경우
	if(depth == r){
    	// 로직 처리
        return;
    }
    
    // input 배열에서 nCr 하여 뽑은 배열을 numbers 배열에 저장
    // 다음 combination을 호출 할 때, 중복 선택이 불가능함으로 i + 1을 넘겨줌
    for(int i = start; i < N; ++i){
    	numbers[depth] = input[i];
        combination(depth + 1, i + 1);
    }
}

재귀 중복 조합

• 순서X, 중복 X

static void combination(int depth, int start){
	// r개의 원소를 뽑은 경우
	if(depth == r){
    	// 로직 처리
        return;
    }
    
    // input 배열에서 nCr 하여 뽑은 배열을 numbers 배열에 저장
    // 다음 combination을 호출 할 때, 중복 선택이므로 i를 넘겨줌
    for(int i = start; i < N; ++i){
    	numbers[depth] = input[i];
        combination(depth + 1, i);
    }
}