C# 백트래킹으로 합이 목표값이 되는 정확히 k개의 고유한 숫자 조합 찾기

이 글에서는 C#의 백트래킹(Backtracking) 기법을 활용하여 1부터 n까지의 숫자 중 정확히 k개의 서로 다른 숫자를 골랐을 때 그 합이 목표값(target)과 일치하는 모든 고유한 조합을 찾는 방법을 살펴봅니다.

문제 예시

예를 들어 n이 5이고 k가 2라고 가정해 보겠습니다. 이 경우 크기가 2인 숫자 조합 중 합이 5가 되는 조합을 찾아야 하며, 결과는 "1,4"와 "2,3" 두 가지입니다.

알고리즘 접근 방식

백트래킹은 재귀 트리를 따라 해답을 탐색하다가 조건에 맞지 않으면 이전 단계로 되돌아가는 기법입니다. 구현 절차는 다음과 같습니다.

유효한 조합을 저장할 출력 리스트(output)와, 재귀 트리의 현재 경로에 해당하는 수열을 담을 현재 리스트(current list)를 생성합니다.
백트래킹 함수는 목표값에 도달할 때까지 재귀적으로 탐색을 이어가며, 합이 목표값을 초과하거나 더 이상 진행할 수 없으면 이전 단계로 되돌아갑니다.
탐색 중 어느 시점에서든 합이 목표값과 같아지고 선택된 숫자의 개수가 정확히 k개라면, 현재까지의 후보 배열을 결과 리스트에 추가합니다.
그 외의 경우에는 후보 배열의 요소를 하나씩 추가하며 재귀 호출을 진행합니다. 이때 다음 탐색 시작 인덱스를 현재 인덱스 + 1로 지정하여 같은 숫자가 중복 선택되지 않도록 합니다.

C# 구현 예제

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
    public class BackTracking{
        public void UniqueCombinationSumOfExactKNumbers(int n, int k){
            int[] array = new int[n];
            for (int i = 0; i < n; i++){
                array[i] = i + 1;
            }
            List<int> currentList = new List<int>();
            List<List<int>> output = new List<List<int>>();
            UniqueCombinationSumOfExactKNumbers(array, n, k, 0, 0, currentList, output);
            foreach (var item in output){
                StringBuilder s = new StringBuilder();
                foreach (var item1 in item){
                    s.Append(item1.ToString());
                }
                Console.WriteLine(s);
                s = null;
            }
        }
        private void UniqueCombinationSumOfExactKNumbers(int[] array, int target, int countOfNumbers, int sum, int index, List<int> currentList, List<List<int>> output){
            if (sum == target){
                if (currentList.Count == countOfNumbers){
                    List<int> newList = new List<int>();
                    newList.AddRange(currentList);
                    output.Add(newList);
                    return;
                }
            }
            else if (sum > target){
                return;
            }
            else if (currentList.Count == countOfNumbers && sum != target){
                return;
            }
            else{
                for (int i = index; i < array.Length; i++){
                    currentList.Add(array[i]);
                    UniqueCombinationSumOfExactKNumbers(array, target, countOfNumbers, sum + array[i], i + 1, currentList, output);
                    currentList.Remove(array[i]);
                }
            }
        }
    }
    class Program{
        static void Main(string[] args){
            BackTracking b = new BackTracking();
            b.UniqueCombinationSumOfExactKNumbers(5, 2);
        }
    }
}

실행 결과

14
23

코드 동작 원리

Main 메서드에서는 n=5, k=2 값으로 메서드를 호출합니다. 먼저 1부터 n까지의 숫자로 구성된 후보 배열을 만들고, 비어 있는 현재 리스트와 출력 리스트를 준비한 뒤 재귀 함수를 실행합니다.

재귀 함수 내부에서는 세 가지 상태를 검사합니다. 첫째, 합이 목표값과 같고 선택된 숫자가 정확히 k개면 현재 조합을 새 리스트로 복사하여 결과에 추가합니다. 둘째, 합이 목표값을 초과하면 더 이상 탐색할 필요가 없으므로 즉시 반환합니다. 셋째, 숫자를 k개 모두 선택했는데도 합이 목표값과 다르면 해당 경로를 폐기합니다.

어떤 종료 조건에도 해당하지 않으면 for 루프를 통해 아직 선택하지 않은 후보 숫자를 하나씩 현재 리스트에 추가하며 재귀 탐색을 계속합니다. 재귀 호출이 반환되면 방금 추가한 숫자를 다시 제거하는데, 이 과정이 바로 백트래킹입니다. 이를 통해 같은 시작점에서 다른 숫자를 선택하는 또 다른 경로를 탐색할 수 있으며, 최종적으로 가능한 모든 고유한 조합이 결과에 수집됩니다.