কিভাবে 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);
      }
   }
}

আউটপুট