combination ( nCr ) (배열, 선택체크배열, 현재index, 선택 필요갯수 r, 현재 선택갯수 c)
만약 선택한 갯수가 r이면 선택완료
선택한것 출력후 return;
만약 index가 배열의 범위 밖이면 선택 불가능
return;
현재 index 선택했다고 표기
combination 호출 ( 다음 index에 대하여, 선택 갯수 +1 )
현재 index 선택하지 않았다고 표기
combination 호출 ( 다음 index에 대하여, 선택갯수 그대로 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone {
public static void main(String[] ar){
Ideone ex = new Ideone();
int[] arr = { 1, 2, 3, 4 };
int r = 3;
int checkCount = 0;
boolean[] selected = new boolean[arr.length];
int startIndex = 0;
combination(arr,selected,0,r,0);
}
public static void combination(int[] arr,boolean[] selected, int index ,int r , int checkCount){
if(checkCount == r){
for(int i = 0; i < arr.length; ++i){
if(selected[i]){
System.out.print(arr[i]+" ");
}
}
System.out.println();
return;
}
if(index == arr.length){
return;
}
selected[index] = true;
combination(arr,selected, index+1, r, checkCount+1);
selected[index] = false;
combination(arr,selected, index+1, r, checkCount);
}
}
| cs |
댓글 없음:
댓글 쓰기