C#을 사용하여 역추적하여 주어진 배열에서 목표 합계를 찾는 방법은 무엇입니까?

<시간/>

목표 합 문제는 요소의 합이 주어진 숫자와 같도록 부분 집합을 찾는 문제입니다. 역추적 접근 방식은 최악의 경우 모든 순열을 생성하지만 일반적으로 부분 집합 합계 문제에 대한 재귀적 접근 방식보다 더 나은 성능을 보입니다.

n개의 양의 정수의 부분집합 A와 값 합이 주어졌을 때, 주어진 집합의 부분집합이 존재하는지 여부를 구하고, 그 요소의 합은 주어진 합과 같은 값

배열 [1,2,3]이 있다고 가정하면 출력은 "1,1,1,1 ", "1,1,2","2,2","13"이 됩니다. 출력 "31"에서 "211" ,"121"은 버릴 수 있습니다.

예시

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);
      }
   }
}

출력