लक्ष्य योग समस्या एक सबसेट खोजने की समस्या है जैसे कि एलिमेंट का योग दी गई संख्या के बराबर हो। बैकट्रैकिंग दृष्टिकोण सबसे खराब स्थिति में सभी क्रमपरिवर्तन उत्पन्न करता है लेकिन सामान्य तौर पर, सबसेट योग समस्या के प्रति रिकर्सिव दृष्टिकोण से बेहतर प्रदर्शन करता है।
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
