문자열의 모든 하위 시퀀스 출력하기: 재귀와 반복을 활용한 3가지 방법

이 문제에서는 하나의 문자열이 주어지고, 그 문자열의 모든 하위 시퀀스(subsequence, 부분 수열)를 출력해야 합니다. 하위 시퀀스는 원본 문자열에서 일부 문자를 삭제하여 만들어지며, 문자들의 순서는 반드시 유지되어야 합니다(즉, 순서를 재배열할 수 없습니다).

예시를 통해 개념을 더 쉽게 이해해 보겠습니다.

입력: xyz
출력: x, y, z, xy, yz, xz, xyz

설명 − 위 예제에서 알 수 있듯이, 하위 시퀀스는 문자를 삭제하는 방식으로만 만들어지며 어떠한 재배열도 일어나지 않습니다. 참고로 길이가 n인 문자열의 하위 시퀀스는 공집합을 포함하여 최대 2ⁿ개까지 존재할 수 있습니다.

이 문제는 여러 가지 방법으로 해결할 수 있습니다. 여기서는 대표적인 세 가지 방법을 살펴보겠습니다. 아래 예제 코드는 Java로 작성되었지만, 동일한 로직은 C++ 등 다른 언어로도 손쉽게 옮겨 적용할 수 있습니다.

방법 1: 문자를 선택하거나 제거하는 재귀 방식

첫 번째 방법은 문자열의 각 문자를 결과에 포함할지 말지를 재귀적으로 결정하는 것입니다. 즉, 몇 개의 문자를 선택하고 나머지는 버려서 하위 시퀀스를 만듭니다. 문자열이 빈 문자열이 되면 지금까지 누적된 문자열을 결과 목록(ArrayList)에 추가합니다.

import java.util.*;
class Main{
    public static ArrayList<String>subStringSeq=new ArrayList<String>();
    public static void main(String[] args) {
        String s="pqrs";
        System.out.println("All the substring found are :");
        findSubString(s,"");
        System.out.println(subStringSeq);
    }
    public static void findSubString(String s, String ans) {
        if(s.length()==0){
            subStringSeq.add(ans);
            return;
        }
        findSubString(s.substring(1),ans+s.charAt(0)) ;
        findSubString(s.substring(1),ans);
    }
}

실행 결과

발견된 모든 하위 시퀀스 −

[pqrs, pqr, pqs, pq, prs, pr, ps, p, qrs, qr, qs, q, rs, r, s]

방법 2: 반복문과 HashSet을 활용한 방식

두 번째 방법은 문자열을 반복문으로 순회하며 부분 문자열을 생성하고, 생성된 문자열에서 문자를 하나씩 제거해 가며 새로운 하위 시퀀스를 만드는 것입니다. 이때 HashSet을 사용해 이미 발견된 하위 시퀀스인지 검사함으로써 중복 생성을 방지합니다.

import java.util.HashSet;
public class Main{
    static HashSet<String> subString = new HashSet<>();
    static void findSubString(String str){
        for (int i = 0; i < str.length(); i++) {
            for (int j = str.length(); j > i; j--) {
                String sub_str = str.substring(i, j);
                if (!subString.contains(sub_str))
                    subString.add(sub_str);
                for (int k = 1; k < sub_str.length() - 1; k++) {
                    StringBuffer sb = new StringBuffer(sub_str);
                    sb.deleteCharAt(k);
                    if (!subString.contains(sb));
                        findSubString(sb.toString());
                }
            }
        }
    }
    public static void main(String[] args){
        String s = "pqrs";
        System.out.println("The subsequence is ");
        findSubString(s);
        System.out.println(subString);
    }
}

실행 결과

하위 시퀀스 −

[rs, pq, qr, pr, qs, ps, prs, p, pqr, q, r, s, pqs, qrs, pqrs]

방법 3: 문자를 고정한 뒤 재귀 호출하는 방식

세 번째 방법은 문자열의 문자를 하나씩 고정하고, 고정된 문자들을 시작점으로 삼아 하위 시퀀스를 찾는 것입니다. 이 메서드를 재귀적으로 계속 호출하면 필요한 모든 문자열 하위 시퀀스가 자연스럽게 생성됩니다.

class Main {
    static void subString(String str, int n,
    int index, String curr){
        if (index == n){
            return;
        }
        System.out.print(curr + ", ");
        for (int i = index + 1; i < n; i++){
            curr += str.charAt(i);
            subString(str, n, i, curr);
            curr = curr.substring(0, curr.length() - 1);
        }
    }
    static void printSubStrings(String str){
        int index = -1;
        String curr = "";
        subString(str, str.length(), index, curr);
    }
    public static void main(String[] args){
        String str = "pqrs";
        System.out.println("The subStrings are :") ;
        printSubStrings(str);
    }
}

실행 결과

하위 문자열들 −

p, pq, pqr, pqrs, pqs, pr, prs, ps, q, qr, qrs, qs, r, rs, s

마무리

세 가지 방법은 모두 같은 문제를 해결하지만 접근 방식이 서로 다릅니다. 첫 번째 방법은 각 문자를 '포함/제외'하는 이진 선택을 재귀로 구현한 것이고, 두 번째 방법은 반복문과 HashSet으로 중복을 관리하며, 세 번째 방법은 시작 문자를 고정한 뒤 한 글자씩 확장해 나가는 방식입니다. 단, 하위 시퀀스의 개수는 입력 길이 n에 대해 최대 2ⁿ개까지 늘어날 수 있으므로, 문자열이 길어질수록 시간과 메모리 사용량이 지수적으로 증가한다는 점을 반드시 유의해야 합니다.