Find Distinct Subsets from an Array Using Backtracking

Distinct subsets problem gives us the different combination from the given array.

When the target is 2 then from the array, we take all the combination that corresponds to number 2, When the target is three then from the array, we take all the combination that corresponds to count 3. In the below example the array is [1,2,3] and the target is 2. So, we take all the combinations the corresponds to number 2 “1,2 “, “2,3”,”1,3””.

Example

 Live Demo

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
   public class BackTracking{
      public void Subsets(int[] array){
         List<int> currentList = new List<int>();
         List<string> results = new List<string>();
         BackTrackkingCombination(array, 2, 0, currentList, results);
         foreach (var item in results){
            StringBuilder s = new StringBuilder();
            foreach (var item1 in item){
               s.Append(item1.ToString());
            }
            Console.WriteLine(s);
            s = null;
         }
      }
      public void BackTrackkingCombination(int[] array, int size, int startIndex, List<int> currentList, List<string> results){
         if (currentList.Count == size){
            StringBuilder s = new StringBuilder();
            foreach (var item in currentList){
               s.Append(item);
            }
            results.Add(s.ToString());
            return;
         }
         for (int i = startIndex; i < array.Length; i++){
            currentList.Add(array[i]);
            BackTrackkingCombination(array, size, i + 1, currentList, results); ;
            currentList.Remove(array[i]);
         }
      }
   }
   class Program{
      static void Main(string[] args){
         BackTracking b = new BackTracking();
         int[] arrs = { 1, 2, 3 };
         b.Subsets(arrs);
      }
   }
}

Output

12
13
23