조합 nCr

① 조합

   : 순서X, 중복X ('중복'은 자기자신 포함 여부를 의미)

 

   예) 1,2,3,4 중 2개 뽑는 경우

        (1,2) (1,3) (1,4) (2,3) (2,4) (3,4)

 

/*
N : 총 숫자 개수(num.length)
R : 숫자 중에서 뽑는 개수 (nCr에서 r을 의미)
int[] num : 숫자 집합 
int[] ans : 조합(nCr) 결과를 담는 베열
int num_index : num[]의 인덱스
int ans_index : ans[]의 인덱스
int cnt : 숫자가 포함될 경우 카운트하는 변수

1. 숫자를 포함하는 경우
   기존의 num[]배열의 인덱스 증가 / 결과 ans[]배열의 인덱스 증가 / 카운트 증가
2. 숫자를 포함하지 않는 경우
   기존의 num[]배열의 인덱스 증가 / 결과 ans[]배열의 인덱스 변화없음 / 카운트 변화없음
*/

private static void combination(int[] num, int[] ans, int num_index, int ans_index, int cnt){
	if(cnt == R){
		for(int i=0; i<ans.length; i++){
			System.out.print(ans[i]+" ");
		}
		System.out.println();
		return;
	}
	if(num_index>=N)
    			return;

	ans[ans_index] = num[num_index];
	combination(num, ans, num_index+1, ans_index+1, cnt+1); //포함
	combination(num, ans, num_index+1, ans_index, cnt); //포함X
}

 

 

 

 

② 중복 조합

   : 순서X, 중복O

 

   예) 1,2,3,4 중 2개 뽑는 경우

        (1,1) (1,2) (1,3) (1,4) (2,2) (2,3) (2,4) (3,3) (3,4) (4,4)

 

/*
N : 총 숫자 개수(num.length)
R : 숫자 중에서 뽑는 개수 (nCr에서 r을 의미)
int[] num : 숫자 집합 
int[] ans : 조합(nCr) 결과를 담는 베열
int num_index : num[]의 인덱스
int ans_index : ans[]의 인덱스
int cnt : 숫자가 포함될 경우 카운트하는 변수

1. 숫자를 포함하는 경우
   기존의 num[]배열의 인덱스 변화없음 / 결과 ans[]배열의 인덱스 증가 / 카운트 증가
2. 숫자를 포함하지 않는 경우
   기존의 num[]배열의 인덱스 증가 / 결과 ans[]배열의 인덱스 변화없음 / 카운트 변화없음
*/

private static void combination(int[] num, int[] ans, int num_index, int ans_index, int cnt){
	if(cnt == R){
		for(int i=0; i<ans.length; i++){
			System.out.print(ans[i]+" ");
		}
		System.out.println();
		return;
	}
	if(num_index>=N)
    			return;

	ans[ans_index] = num[num_index];
	combination(num, ans, num_index, ans_index+1, cnt+1); //포함
	combination(num, ans, num_index+1, ans_index, cnt); //포함X
}