How to find the unique combination of sum from the given number C#?



Create an output list to store the valid sequences, create a current list that will store the current sequence found in the path of the recursion tree. A backtrack function that will go into the recursion until the target is achieved, otherwise, it should backtrack to the previous phase as target becomes less than 0. At any point in time, if target becomes 0 then add the candidate array to the result as the values in the candidate array must be sum up to the given target.

If those are not the

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace CsharpCode_ConsoleApplication{
   public class BackTracking{
      public void UniqueCombinationOfNumbersCorrespondsToSum(int n){
         int[] array = new int[n + 1];
         for (int i = 1; i <= n; i++){
            array[i] = i;}
            List<int> currentList = new List<int>();
            List<List<int>> output = new List<List<int>>();
            UniqueCombinationSum(array, n, 0, 0, currentList, output);
            foreach (var item in output){
               StringBuilder s = new StringBuilder();
               foreach (var item1 in item){
                  s.Append(item1.ToString());
               }
               Console.WriteLine(s);
               s = null;
            }
         }
         private void UniqueCombinationSum(int[] array, int target, int sum, int index, List<int> currentList, List<List<int>> output){
            if (sum == target){
               List<int> newList = new List<int>();
               newList.AddRange(currentList);
               output.Add(newList);
               return;
            }
            else if (sum > target){
               return;
            }
            else{
               for (int i = index; i < array.Length; i++){
                  currentList.Add(array[i]);
                  UniqueCombinationSum(array, target, sum + array[i], i + 1, currentList, output);
                  currentList.Remove(array[i]);
               }
            }
         }
      }
      class CsharpCode_Program{
         static void Main(string[] args){
            BackTracking b = new BackTracking();
            b.UniqueCombinationOfNumbersCorrespondsToSum(5);
         }
      }  
   }
}

0 Comment's

Comment Form

Submit Comment