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

出力

1111
112
13
22