고유한 부분집합(Distinct Subsets) 문제는 주어진 배열의 원소들로 만들 수 있는 서로 다른 조합을 모두 찾아내는 문제입니다.
목표 크기가 2라면 배열에서 2개의 원소를 선택하는 모든 조합을, 목표 크기가 3이라면 3개의 원소를 선택하는 모든 조합을 구합니다. 예를 들어 배열이 [1, 2, 3]이고 목표 크기가 2라면 "1,2", "1,3", "2,3" 세 가지 조합이 결과로 출력됩니다.
백트래킹의 동작 원리
이 문제는 백트래킹(Backtracking) 기법으로 효율적으로 해결할 수 있습니다. 백트래킹은 가능한 모든 후보를 체계적으로 탐색하다가, 조건을 만족하면 결과를 저장하고 이전 단계로 되돌아가 다른 경로를 계속 시도하는 방식입니다. 알고리즘의 흐름은 다음과 같습니다.
- 선택: 시작 인덱스(startIndex)부터 배열을 순회하며 현재 리스트(currentList)에 원소를 하나씩 추가합니다.
- 종료 조건 확인: 현재 리스트의 크기가 목표 크기(size)에 도달하면 해당 조합을 문자열로 만들어 결과 리스트(results)에 저장합니다.
- 재귀 탐색: 다음 인덱스(i + 1)를 시작점으로 재귀 호출하여 나머지 원소들을 탐색합니다. 이렇게 하면 같은 원소를 중복해서 선택하지 않습니다.
- 백트래킹(선택 취소): 재귀 호출이 반환되면 방금 추가한 원소를 제거하여, 다음 반복에서 다른 원소를 시도할 수 있도록 합니다.
예제 코드
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication {
public class BackTracking {
public void Subsets(int[] array) {
List<int> currentList = new List<int>();
List<string> results = new List<string>();
// 목표 크기가 2인 모든 조합 탐색
BacktrackCombination(array, 2, 0, currentList, results);
// 결과 출력
foreach (var result in results) {
Console.WriteLine(result);
}
}
public void BacktrackCombination(int[] array, int size, int startIndex,
List<int> currentList, List<string> results) {
// 종료 조건: 목표 크기에 도달하면 현재 조합을 저장
if (currentList.Count == size) {
StringBuilder sb = new StringBuilder();
foreach (var num in currentList) {
sb.Append(num);
}
results.Add(sb.ToString());
return;
}
// startIndex부터 탐색하여 중복 조합 방지
for (int i = startIndex; i < array.Length; i++) {
currentList.Add(array[i]); // 1. 선택
BacktrackCombination(array, size, i + 1, currentList, results); // 2. 재귀 탐색
currentList.Remove(array[i]); // 3. 백트래킹(선택 취소)
}
}
}
class Program {
static void Main(string[] args) {
BackTracking b = new BackTracking();
int[] arrs = { 1, 2, 3 };
b.Subsets(arrs);
}
}
}
실행 결과
12 13 23
코드 설명 및 참고 사항
Main 메서드에서 배열 { 1, 2, 3 }과 목표 크기 2를 전달하면, 재귀 함수가 깊이 우선 방식으로 모든 조합을 탐색합니다. 조합이 완성될 때마다 StringBuilder로 원소들을 이어 붙여 문자열로 저장하고, 최종적으로 콘솔에 한 줄씩 출력합니다.
배열의 길이가 n이고 목표 크기가 k일 때 만들어지는 조합의 개수는 이항계수 C(n, k)와 같습니다. 따라서 위 예제에서는 C(3, 2) = 3개의 결과가 출력됩니다. 참고로 배열에 중복된 값이 포함될 가능성이 있다면 currentList.Remove(array[i])처럼 값을 기준으로 제거하는 대신, RemoveAt(currentList.Count - 1)처럼 마지막 인덱스를 직접 제거하는 방식이 더 안전합니다.