C#에서 주어진 합계에 해당하는 고유한 숫자 조합을 찾는 방법

C#에서 주어진 합계에 해당하는 고유한 숫자 조합 찾기

주어진 숫자의 합이 되는 고유한 숫자 조합을 찾으려면 백트래킹(Backtracking) 기법을 활용하는 것이 효과적입니다. 먼저 유효한 수열을 저장할 출력 리스트(output list)를 만들고, 재귀 트리 탐색 경로에서 발견된 현재 수열을 저장할 현재 리스트(current list)를 생성합니다.

백트래킹 함수는 목표값(target)에 도달할 때까지 재귀 호출을 반복하며, 탐색 중 합계가 목표값을 벗어나면 이전 단계로 되돌아갑니다. 언제든지 남은 목표값이 정확히 0이 되면, 후보 배열의 값들을 모두 더했을 때 주어진 목표값과 일치한다는 의미이므로 해당 후보 배열을 결과에 추가합니다.

그 외의 경우에는 후보 배열의 요소를 하나씩 현재 리스트에 추가하면서 재귀적으로 탐색을 계속 진행합니다.

동작 예시

예를 들어 숫자가 5라면, 합이 5가 되는 숫자 조합을 찾아야 합니다. 이때 기대되는 결과는 "1,4", "2,3", "5"입니다. 다만 아래 예제 코드에서는 배열의 0번 인덱스가 0으로 초기화된 채로 탐색에 포함되기 때문에 "05"처럼 0이 포함된 조합도 함께 출력됩니다. 따라서 최종 결과에서는 0이 포함된 조합을 제외하면 원하는 답을 얻을 수 있습니다.

예제 코드

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

namespace ConsoleApplication {
    public class BackTracking {
        public void UniqueCombinationOfNumbersCorrespondsToSum(int n) {
            // 1부터 n까지의 숫자로 후보 배열 초기화
            int[] array = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                array[i] = i;
            }
            List<int> currentList = new List<int>();
            List<List<int>> output = new List<List<int>>();
            UniqueCombinationSum(array, n, 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 UniqueCombinationSum(int[] array, int target, int sum, int index, List<int> currentList, List<List<int>> output) {
            // 합계가 목표값과 일치하면 현재 조합을 결과에 저장
            if (sum == target) {
                List<int> newList = new List<int>();
                newList.AddRange(currentList);
                output.Add(newList);
                return;
            }
            // 합계가 목표값을 초과하면 해당 경로를 포기하고 백트래킹
            else if (sum > target) {
                return;
            }
            else {
                for (int i = index; i < array.Length; i++) {
                    currentList.Add(array[i]);
                    UniqueCombinationSum(array, target, sum + array[i], i + 1, currentList, output);
                    currentList.Remove(array[i]);
                }
            }
        }
    }

    class Program {
        static void Main(string[] args) {
            BackTracking b = new BackTracking();
            b.UniqueCombinationOfNumbersCorrespondsToSum(5);
        }
    }
}

코드 설명

UniqueCombinationOfNumbersCorrespondsToSum: 1부터 n까지의 숫자로 후보 배열을 초기화한 뒤 백트래킹 함수를 호출하고, 완성된 조합들을 화면에 출력합니다.
UniqueCombinationSum: 현재 합계(sum)가 목표값(target)과 같으면 지금까지 모은 조합을 결과 리스트에 복사해 저장합니다. 합계가 목표값을 초과하면 더 이상 진행할 수 없으므로 해당 경로를 포기하고 되돌아갑니다. 그 외의 경우에는 현재 인덱스부터 배열 끝까지 요소를 하나씩 추가하며 재귀 호출을 수행하고, 호출이 반환되면 마지막에 추가한 요소를 제거하여 다른 경로를 탐색합니다. 이 과정이 바로 백트래킹의 핵심입니다.

실행 결과

14
23
05

실행 결과를 보면 합이 5가 되는 조합인 "14", "23", "05"가 순서대로 출력됩니다. 여기서 0이 포함된 "05"를 제외하면, 실질적인 정답 조합은 "1+4", "2+3", 그리고 숫자 자체인 "5"임을 알 수 있습니다.