목표 합계(Target Sum) 문제는 주어진 배열의 요소들을 조합하여 그 합이 특정 목표값과 일치하는 부분집합을 찾는 고전적인 알고리즘 문제입니다. 백트래킹(backtracking) 기법은 최악의 경우 모든 순열을 탐색하게 되지만, 단순 재귀 방식으로 부분집합 합(subset sum) 문제를 해결하는 것보다 일반적으로 더 나은 성능을 보입니다.
문제 정의
n개의 양의 정수로 이루어진 배열 A와 목표값 sum이 주어졌을 때, 요소들의 합이 sum과 정확히 일치하는 부분집합이 존재하는지 판별하고, 가능한 모든 조합을 구하는 것이 목표입니다.
예를 들어 배열 [1, 2, 3]과 목표값 4가 주어지면 정답은 1111(1+1+1+1), 112(1+1+2), 22(2+2), 13(1+3)의 네 가지입니다. 이때 31, 211, 121처럼 순서만 다른 중복 조합은 결과에서 제외됩니다.
C# 코드 예제
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
public class BackTracking{
public void Combinationsums(int[] array, int target){
List<int> currentList = new List<int>();
List<List<int>> results = new List<List<int>>();
int sum = 0;
int index = 0;
CombinationSum(array, target, currentList, results, sum, index);
foreach (var item in results){
StringBuilder s = new StringBuilder();
foreach (var item1 in item){
s.Append(item1.ToString());
}
Console.WriteLine(s);
s = null;
}
}
private void CombinationSum(int[] array, int target, List<int> currentList, List<List<int>> results, int sum, int index){
if (sum > target){
return;
}
else if (sum == target){
if (!results.Contains(currentList)){
List<int> newList = new List<int>();
newList.AddRange(currentList);
results.Add(newList);
return;
}
}
else{
for (int i = 0; i < array.Length; i++){
currentList.Add(array[i]);
CombinationSum(array, target, currentList, results, sum + array[i], i);
currentList.Remove(array[i]);
}
}
}
}
class Program{
static void Main(string[] args){
BackTracking b = new BackTracking();
int[] arrs = { 1, 2, 3 };
b.Combinationsums(arrs, 4);
}
}
}
출력 결과
1111 112 13 22
알고리즘 동작 원리
- 가지치기: 재귀 탐색 도중 현재까지의 합(sum)이 목표값(target)을 초과하면 해당 경로를 즉시 종료하여 불필요한 탐색을 줄입니다.
- 정답 저장: 합이 목표값과 정확히 일치하면 현재 조합을 새 리스트로 복사해 결과 리스트에 추가합니다.
- 백트래킹: 요소를 하나씩 추가하며 재귀 호출을 진행하고, 탐색이 끝나면 해당 요소를 다시 제거해 다른 경로를 탐색할 수 있도록 합니다.
- 중복 방지: 재귀 호출 시 현재 인덱스 i를 그대로 전달하므로 이미 지나간 인덱스로 되돌아가지 않습니다. 덕분에 31과 13처럼 순서만 다른 중복 조합이 생성되지 않으며, 같은 인덱스를 반복해서 선택할 수 있기 때문에 1을 네 번 사용하는 1111 같은 조합도 가능합니다.