Làm thế nào để tìm tổng mục tiêu từ mảng đã cho bằng cách sử dụng C #?

Bài toán tổng mục tiêu là bài toán tìm một tập hợp con sao cho tổng các phần tử bằng một số nhất định. Phương pháp backtracking tạo ra tất cả các hoán vị trong trường hợp xấu nhất nhưng nhìn chung, hoạt động tốt hơn so với phương pháp đệ quy đối với bài toán tổng tập hợp con.

Một tập hợp con A gồm n số nguyên dương và một tổng giá trị được cho trước, tìm xem có tồn tại bất kỳ tập con nào của tập hợp đã cho hay không, tổng các phần tử của chúng bằng giá trị tổng đã cho

Giả sử chúng ta có một mảng [1,2,3] đầu ra sẽ là “1,1,1,1”, “1,1,2”, “2,2”, ”13” Từ đầu ra “31”, "211", "121" có thể bị loại bỏ

Ví dụ

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

Đầu ra