如何通过使用 C# 回溯从给定数组中找到目标总和？

目标和问题是找到一个子集的问题，使得元素的总和等于给定的数字。回溯方法在最坏的情况下生成所有排列，但一般来说，在解决子集和问题时比递归方法表现更好。

给定n个正整数的子集A和一个值和，求给定集合的任何子集是否存在，其元素之和等于给定的sum值

假设我们有一个数组 [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