सी # का उपयोग करके बैकट्रैकिंग द्वारा दिए गए सरणी से लक्ष्य राशि कैसे प्राप्त करें?

लक्ष्य योग समस्या एक उपसमुच्चय को खोजने की समस्या है जैसे कि तत्वों का योग एक दी गई संख्या के बराबर हो। बैकट्रैकिंग दृष्टिकोण सबसे खराब स्थिति में सभी क्रमपरिवर्तन उत्पन्न करता है लेकिन सामान्य तौर पर, सबसेट सम समस्या के लिए पुनरावर्ती दृष्टिकोण से बेहतर प्रदर्शन करता है।

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

आउटपुट