[JAVA] 순열, 중복순열, 조합, 중복조합

DFS + Backtracking  을 이용한 구현

---

DFS (Depth-First Search, 깊이 우선 탐색)

• 트리나 그래프를 탐색하는 방식 중 하나
• 한 갈래를 끝까지 파고든 뒤, 막히면 되돌아가서 다른 갈래 탐색
• 재귀 함수나 스택으로 구현 가능

백트래킹 (Backtracking)

• DFS의 일종의 응용 기법
• 어떤 조건을 만족하지 않으면, 그 분기에서 더 이상 탐색하지 않고 되돌아감(백트랙)
• 즉, 가능성이 없는 경로는 일찍 포기함으로써 탐색 효율을 높임

 

순열/조합은 가능한 모든 경우를 탐색 - > DFS

조건(중복 방지, 순서 조건 등)에 맞지 않는 경우를 잘라냄(Pruning) -> Backtracking  

---

관련 문제

백준 N과 M 시리즈

https://www.acmicpc.net/workbook/view/7315

---

 

1. 순열 (Permutation)

• 중복 X, 순서 O
• 예: [1, 2, 3] → (1,2), (2,1), (1,3) 등
• 조건: 같은 숫자 여러 번 사용 불가

void perm(int[] arr, boolean[] visited, List<Integer> result, int depth, int r) {
    if (depth == r) {
        System.out.println(result);
        return;
    }

    for (int i = 0; i < arr.length; i++) {
        if (!visited[i]) {
            visited[i] = true;
            result.add(arr[i]);
            perm(arr, visited, result, depth + 1, r);
            result.remove(result.size() - 1);
            visited[i] = false;
        }
    }
}

 

 

• visited: 숫자 사용 여부 체킹용 ( 중복 방지 ) 
• result: 현재까지 만든 순열
• depth: 현재까지 선택한 개수
• r: 만들 순열의 길이

1. depth == r이면 순열 완성 → 출력 (문제에서 요구하는 방식마다 수정 가능) ,return 으로 재귀 종료
2. 모든 숫자 경우의 수 돌면서:
   • 아직 사용 안 한 숫자라면 ( 사용한 숫자를 다시 사용하면 중복이므로 ) 
     • 방문 체크 → 결과에 추가
     • 다음 단계로 재귀 호출
     • 재귀 끝나면 되돌리기 ( 이전 트리 탐색 정보 삭제 )
       • result remove -> 결과값 삭제 의미 ex ) [a,b,c,d] 에서 a,b,c 탐색 완료. 이후 c 삭제하고 d에 탐색 진행 a,b,d
       • visited  false -> 중복 체킹한것 초기

 

---

2. 중복 순열 (Permutation with Repetition)

• 중복 O, 순서 O
• 예: [1, 2] → (1,1), (1,2), (2,1), (2,2)
• 조건: 같은 숫자 여러 번 사용 가능

void dupPerm(int[] arr, List<Integer> result, int depth, int r) {
    if (depth == r) {
        System.out.println(result);
        return;
    }

    for (int i = 0; i < arr.length; i++) {
        result.add(arr[i]);
        dupPerm(arr, result, depth + 1, r);
        result.remove(result.size() - 1);
    }
}

 

 

• arr: 사용할 숫자들
• result: 현재까지 만든 숫자 조합
• depth: 현재까지 선택한 개수
• r: 만들 조합의 길이

순열과 중복순열의 차이점 ? - visited 배열을 통한 체킹 없음 (중복 선택 허용을 의미)

 

1. depth == r이면 중복 순열 완성 → 출력 (문제에서 요구하는 방식마다 수정 가능) ,return 으로 재귀 종료
2. 모든 숫자 경우의 수 돌면서 :
   • 선택해서 결과에 추가
   • 다음 단계로 재귀 호출
   • 재귀 끝나면 되돌리기 ( 이전 트리 탐색 정보 삭제 )

 

---

순열과 조합의 차이점?

 

• 순열 : 반복문의 시작 인덱스는 0부터 시작 
  • ex) [a,b,c,d] 에 있어 a,b | a,c | a,d 탐색 완료 후 b -> a(0번 인덱스) 가능 b,a, | b,c | b,d 
  • 즉, a,b 와 b,a가 가능함으로써 순서가 다르면 다른 케이스로 분류
• 조합 : 인덱스 매개 변수( start ) 를 통해 반복문 시작 인덱스 조절 ( for i= start ...)
  • ex) [a,b,c,d] 에 있어 a,b | a,c | a,d 탐색 완료 후 b -> c(start번 인덱스) 가능 b,c | b,d
  • 즉, start 매개변수를 통해 무조건 다음 인덱스 원소에 대해 탐색.
    순서가 다르면 같은 케이스이므로 이전 인덱스는 탐색 안함

3. 조합 (Combination)

• 중복 X, 순서 X
• 예: [1, 2, 3] → (1,2), (1,3), (2,3)
• 조건: 이전에 선택한 인덱스 이후만 탐색

void comb(int[] arr, List<Integer> result, int depth, int start, int r) {
    if (depth == r) {
        System.out.println(result);
        return;
    }

    for (int i = start; i < arr.length; i++) {
        result.add(arr[i]);
        comb(arr, result, depth + 1, i + 1, r);
        result.remove(result.size() - 1);
    }
}

 

• arr: 사용할 숫자들
• result: 현재까지 만든 조합
• depth: 현재까지 선택한 개수
• start: 다음에 선택할 숫자의 시작 인덱스 (중복 방지용)
• r: 만들 조합의 길이

1. depth == r이면 조합 완성 → 출력하고 리턴
2. start부터 arr.length까지:
   • 숫자 선택 → 결과에 추가
   • 재귀 호출 (start를 현재 인덱스 + 1로 넘김) -> 이미 탐색 진행한 인덱스는 탐색을 안함으로써 순서를 없앰
   • 되돌리기 (remove)

 

---

 

 

4. 중복 조합 (Combination with Repetition)

• 중복 O, 순서 X
• 예: [1, 2] → (1,1), (1,2), (2,2)
• 조건: 같은 인덱스부터 탐색 가능

void dupComb(int[] arr, List<Integer> result, int depth, int start, int r) {
    if (depth == r) {
        System.out.println(result);
        return;
    }

    for (int i = start; i < arr.length; i++) {
        result.add(arr[i]);
        dupComb(arr, result, depth + 1, i, r);
        result.remove(result.size() - 1);
    }
}

 

 

조합과 중복조합의 차이점 ? - start 인덱스를 그대로 유지해서 같은 숫자 반복 선택 가능하게 함 ( 중복 허용 )

 

• arr: 사용할 숫자들
• result: 현재까지 만든 조합
• depth: 현재까지 선택한 개수
• start: 다음에 선택할 숫자의 시작 인덱스
• r: 만들 조합의 길이

 

• depth == r이면 중복 조합 완성 → 출력하고 리턴
• start부터 arr.length까지:
  • 숫자 선택 → 결과에 추가
  • 재귀 호출 (start를 그대로 넘김) ← 중복 허용 포인트
  • 되돌리기 (remove)

 

 

 

---