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

 

  1. 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 
    1. static void Main(string[] args)   
    2. {  
    3.     //Get the length of array from the user  
    4.     Console.Write("Eneter the length of an array:");  
    5.     int len = Convert.ToInt32(Console.ReadLine());  
    6.   
    7.     //Create an array of given length  
    8.     int[] arr = new int[len];  
    9.   
    10.     //Get the value from the user an save them to the array  
    11.     for (int i = 0; i < len; i++)  
    12.     arr[i] = Convert.ToInt32(Console.ReadLine());  
    13.   
    14.     //Get the sum  
    15.     Console.Write("Eneter the required sum:");  
    16.     int sum = Convert.ToInt32(Console.ReadLine());  
    17. }  


  2. Write the code in a function to get all the possible unique substrings from the input string.
    1. private static void FindRequiredSumSubArray(int[] arr, int sum)   
    2. {  
    3.     //create an array for the subset with max length od input array  
    4.     int[] sub = new int[arr.Length];  
    5.     int temp = 0;  
    6.     for (int i = 0; i < arr.Length; i++)   
    7.     {  
    8.         for (int j = i, col = 0; j < arr.Length; j++, col++)  
    9.         {  
    10.             //add the value of input array one by one  
    11.             temp += arr[j];  
    12.             sub[col] = arr[j];  
    13.             //if addition is equal to sum then print it  
    14.             if (temp == sum)   
    15.             {  
    16.                 int total = 0;  
    17.                 for (int k = 0; k < sub.Length; k++)   
    18.                 {  
    19.                     total += sub[k];  
    20.                     Console.Write(sub[k].ToString() + " ");  
    21.   
    22.                     //if total and sum are equal then leave the print  
    23.                     if (total == sum) 
    24.                     {  
    25.                         Console.Write("\n");  
    26.                         break;  
    27.                     }  
    28.                 }  
    29.             }  
    30.             //if temp is greater than sum are equal then clear the sub array, set temp value and leave the loop for next  
    31.             if (temp > sum)   
    32.             {  
    33.                 Array.Clear(sub, 0, sub.Length);  
    34.                 temp = 0;  
    35.                 break;  
    36.             }  
    37.         }  
    38.     }  
    39. }  


  3. Call the function with the 2 parameters, array and sum in the main() method.
    1. Console.WriteLine("Output String is:");  
    2. FindRequiredSumSubArray(arr, sum);  
    3. 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