Find Target Sum Using Backtracking in C#

Target sum problem is the problem of finding a subset such that the sum of elements equal a given number. The backtracking approach generates all permutations in the worst case but in general, performs better than the recursive approach towards subset sum problem.

A subset A of n positive integers and a value sum is given, find whether or not there exists any subset of the given set, the sum of whose elements is equal to the given value of sum

Suppose we have an array [1,2,3] the output will be “1,1,1,1 “, “1,1,2”,”2,2”,”13” From the output “31 ”,”211” ,”121” can be discarded

Example

 Live Demo

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

Output

1111
112
13
22