How to Get the Subsets From an Array That Are Equal to Input Value

Introduction 

A program that will get an input array with an integer sum and provide the possible subsets from that array of the elements equal to the integer values specifeid as "requiredSum".

Programmers ususally go to an interview and the company asks to write the code of some program to check your logic and coding abilities.

You can write the code in any language like C, C++, Java, C# and so on. There is no required language and technology because the company wants to check your ability to think, your skills to write the code.

Some companies only want the algorithm to check your skills.

One of the programs in those common programs is the following.

Question

You are given an array of integers. Write a function to find a list of sub-sets within the given array sum of whose elements are equal to the given integer "requiredSum". If more than one such sub-set exists then find all of them.

For Example

Input array = [ 1, 2, 3, 4, 5, 6, 7]
requiredSum= 12
output = [ 3, 4, 5]

Input array = [ 6, 2, 3, 10, 5, 9, 12]
requiredSum= 21
output = [ 6, 2, 3, 10] and [ 9, 12]

Function Prototype

 

void FindRequiredSumSubArray(int[ ] array, int requiredSum)

To do this, I will use Visual Studio 2012 as an IDE and C# as a language.

Create a new console application named "ConsoleApplication1".

Where you will get the page that will look like:

Now I will provide the procedure for creating the code.

1. Add the following code to the main() method to get some input from the user.
   
      - Get the length of the array
      - Create the array of the given length
      - Get the values of the array
      - Get the sum　
   

   static void Main(string[] args)
   {
       //Get the length of array from the user
       Console.Write("Eneter the length of an array:");
       int len = Convert.ToInt32(Console.ReadLine());
   
       //Create an array of given length
       int[] arr = new int[len];
   
       //Get the value from the user an save them to the array
       for (int i = 0; i < len; i++)
       arr[i] = Convert.ToInt32(Console.ReadLine());
   
       //Get the sum
       Console.Write("Eneter the required sum:");
       int sum = Convert.ToInt32(Console.ReadLine());
   }

   
   
   
2. Write the code in a function to get all the possible unique substrings from the input string.
   

   private static void FindRequiredSumSubArray(int[] arr, int sum)
   {
       //create an array for the subset with max length od input array
       int[] sub = new int[arr.Length];
       int temp = 0;
       for (int i = 0; i < arr.Length; i++)
       {
           for (int j = i, col = 0; j < arr.Length; j++, col++)
           {
               //add the value of input array one by one
               temp += arr[j];
               sub[col] = arr[j];
               //if addition is equal to sum then print it
               if (temp == sum)
               {
                   int total = 0;
                   for (int k = 0; k < sub.Length; k++)
                   {
                       total += sub[k];
                       Console.Write(sub[k].ToString() + " ");
   
                       //if total and sum are equal then leave the print
                       if (total == sum)
                       {
                           Console.Write("\n");
                           break;
                       }
                   }
               }
               //if temp is greater than sum are equal then clear the sub array, set temp value and leave the loop for next
               if (temp > sum)
               {
                   Array.Clear(sub, 0, sub.Length);
                   temp = 0;
                   break;
               }
           }
       }
   }

   
   
   
3. Call the function with the 2 parameters, array and sum in the main() method.
   

   Console.WriteLine("Output String is:");
   FindRequiredSumSubArray(arr, sum);
   Console.ReadKey();

Result

1. If I provide ”7” as the length, “1,2,3,4,5,6,7” as values and "12" as the sum then the output will be like:
   
   Output: 3 4 5
   
   
   
   
2. If I provide ”7” as the length, “6,2,3,10,5,9,12” as values and "21" as the sum then the output will be like:
   
   Output: 6 2 3 10
                  9 12