728x90
import java.util.HashSet;
import java.util.Set;
/**
* Recursive
*/
public class Recursive {
static Set<Integer> subSet = new HashSet<>();
static int n = 3;
static Set<Integer> permutation = new HashSet<>();
static boolean[] visited;
static int range = 5;
static int size = 3;
public static void main(String[] args) {
makeSubSet(1);
visited = new boolean[range + 1];
makePermutation(1);
}
static void makeSubSet(int k) {
// 부분집합을 처리
if (k == n + 1) {
StringBuilder stringBuilder = new StringBuilder();
for (Integer i : subSet) {
stringBuilder.append(i + " ");
}
System.out.println(stringBuilder.toString().trim());
return;
}
// k를 부분집합에 포함시키는 경우
subSet.add(k);
makeSubSet(k + 1);
subSet.remove(k);
// k를 부분집합에 포함시키지 않는 경우
makeSubSet(k + 1);
}
// 원소가 size인 순열 생성하기
static void makePermutation(int k) {
// 부분순열을 처리
if (permutation.size() == size) {
StringBuilder stringBuilder = new StringBuilder();
for (Integer i : permutation) {
stringBuilder.append(i + " ");
}
System.out.println(stringBuilder.toString().trim());
return;
}
// 순열의 원소가 될 수 있는 수를 순회하면서 순열 생성
for (int i = k; i <= range; i++) {
if (visited[i])
continue;
visited[i] = true;
permutation.add(i);
makePermutation(i + 1);
visited[i] = false;
permutation.remove(i);
}
}
}
'Problem Solving > 알고리즘' 카테고리의 다른 글
이분 탐색(Binary Search) (0) | 2022.04.23 |
---|---|
퀵 정렬(Quick Sort) (0) | 2021.06.18 |
쉘 정렬(Shell Sort) (0) | 2021.06.18 |
삽입 정렬(Insertion Sort) (0) | 2021.06.13 |
선택 정렬(Selection Sort) (0) | 2021.06.07 |