[알고리즘] 순열, 중복순열, 조합, 중복조합 총 정리 (Java, 자바)

이번 포스팅에서는 코딩 테스트를 풀다 보면 정말 자주 나오는 순열, 중복순열, 조합, 중복조합에 대해 정리해보려고 한다. 순열, 중복순열, 조합, 중복조합은 완전 탐색 문제에서 자주 나오고, 구현하는 방법만 알면 문제를 정말 쉽게 풀 수 있으므로 꼭 알아야 하는 알고리즘이다. 구현은 재귀를 이용한 백트래킹을 사용할 것이다. 개인적으로 이 방법이 가장 깔끔하다고 생각한다. 주의해야 할 점은 시간 복잡도가 굉장히 크므로 n이 10 근처일 때 사용해야 한다. (n이 굉장히 크면 시간 초과 발생) 구현에 앞서서 초기 조건은 다음과 같다. public class Main { static int[] arr = {1, 2, 3, 4}; // n에 해당하는 배열 static int[] output; // r개를 뽑은 ..