C#으로 리스트의 모든 하위 목록(부분 집합) 출력하기

C#에서는 반복문과 List<T>만 활용하면 문자열의 모든 하위 목록(부분 집합)을 손쉽게 생성할 수 있습니다. 이 글에서는 문자열 "xyz"를 예로 들어, 만들 수 있는 모든 조합을 사전순으로 정렬한 뒤 출력하는 방법을 단계별로 살펴봅니다.

1단계: 리스트 생성하기

가장 먼저 결과를 담을 문자열 리스트를 선언합니다.

List<string> list = new List<string>();

2단계: 반복문으로 하위 목록 생성하기

대상 문자열은 "xyz"입니다. 바깥쪽 반복문은 문자열을 한 글자씩 순회하고, 안쪽 반복문에서는 매번 새로운 리스트를 선언하여 기존 요소들 뒤에 새 문자를 붙인 조합을 만들어냅니다. 즉, 조건이 참(true)이 되는 각 반복마다 새로운 하위 목록이 생성되는 구조입니다.

for (int i = 1; i < str.Length; i++) {
    list.Add(str[i - 1].ToString());
    List<string> newlist = new List<string>();
    for (int j = 0; j < list.Count; j++) {
        string list2 = list[j] + str[i];
        newlist.Add(list2);
    }
    list.AddRange(newlist);
}

동작 원리

• 바깥쪽 반복문: 두 번째 문자부터 마지막 문자까지 차례로 확인하며, 바로 앞의 문자를 단독 요소로 리스트에 추가합니다.
• 안쪽 반복문: 지금까지 누적된 모든 하위 목록에 새 문자를 이어 붙여 새로운 조합을 생성합니다.
• AddRange: 새로 만든 조합들을 원래 리스트에 한 번에 병합합니다.
• 마무리 처리: 반복이 끝나면 마지막 문자를 단독 요소로 추가한 뒤, Sort()로 사전순 정렬하고 Environment.NewLine을 기준으로 줄바꿈하여 출력합니다.

전체 예제 코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Demo {
    class MyApplication {
        static void Main(string[] args) {
            string str = "xyz";
            List<string> list = new List<string>();
            for (int i = 1; i < str.Length; i++) {
                list.Add(str[i - 1].ToString());
                List<string> newlist = new List<string>();
                for (int j = 0; j < list.Count; j++) {
                    string list2 = list[j] + str[i];
                    newlist.Add(list2);
                }
                list.AddRange(newlist);
            }
            list.Add(str[str.Length - 1].ToString());
            list.Sort();
            Console.WriteLine(string.Join(Environment.NewLine, list));
        }
    }
}

실행 결과

x
xy
xyz
xz
y
yz
z

참고 사항

길이가 n인 문자열에서 공집합을 제외한 부분 집합의 개수는 2ⁿ − 1개입니다. 위 예제에서는 n = 3이므로 총 7개의 하위 목록이 출력됩니다. 다만 입력 크기가 커질수록 조합의 수는 지수적으로 증가하므로, 긴 문자열을 다룰 때는 성능에 유의해야 합니다.