permutation( nPr ) (배열, 선택 체크 배열, 선택 필요 개수 r, 스택)
만약 스택에 들어있는 값의 갯수가 r이면 ( r개 선택 완료 )
스택에 있는 값 출력 (bottom부터 top까지 역순으로 출력해야함)
return;
index <- 배열의 처음( 0 )부터 끝( n-1 )까지 탐색
만약 index가 선택되지 않았다면
index 선택되었다고 표기하고
index에 해당하는 값을 스택에 넣는다.
permutation 호출
index 선택된것 표기 해제
스택에서 pop (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
|
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 };
Stack<Integer> s = new Stack<>();
int r = 2;
boolean[] selected = new boolean[arr.length];
combination(arr,selected,r,s);
}
public static void combination(int[] arr,boolean[] selected, int r, Stack<Integer> s){
if(s.size() == r){
System.out.println(s);
return;
}
for(int i = 0; i < arr.length; ++i){
if(!selected[i]){
selected[i] = true;
s.push(arr[i]);
combination(arr,selected,r,s);
selected[i] = false;
s.pop();
}
}
}
}
| cs |
댓글 없음:
댓글 쓰기