by Given an array and a given SUM, find all the combinations present in the array whose sum is equal to given SUM. Print all such combinations in the array.
For eg:
Let’s assume
int arr[] = {5, 7, 9, 1, 6, 8};
int sum = 15;
Possible combinations are, {7, 8}, {9, 6}
Algorithm
- Iterate through all elements in an array (i)
- Define a hash table with size = 2 * size of array
- Iterate through array from elements j = i+1 to end
- Search in hash table for entry (sum – arr[i] – arr[j])
- If element is found, then print the triplet.
- Else insert the element in hash table.
Before going ahead, have a look at the Hash table classes and its implementation.
class Hashing
{
public:
int* m_hash_table;
int m_entries;
int m_size;
int hash_function (int key);
Hashing (int size);
~Hashing ();
int get_size ();
int get_entries ();
int get_load_factor ();
void insert_data (int data);
void delete_data (int data);
bool search_data (int data);
void print_element ();
};
class HashingDoubleHashing: public Hashing
{
public:
bool disable_log;
HashingDoubleHashing (int size);
HashingDoubleHashing (int size, bool log);
~HashingDoubleHashing ();
int second_hash_function (int key);
void insert_data (int data);
void delete_data (int data);
bool search_data (int data);
};
Let’s have a look at program to solve above problem.
/*
* Given an array of integers and a value,
* determine if there are any three integers in the array
* whose sum is equal to the given value.
*/
#include "iostream"
#include "HashingDoubleHashing.h"
#define ARRAY_MAX_SIZE 50
#define ARRAY_MAX_VALUE 100
using namespace std;
void all_possible_combinations (int *arr, int sum)
{
/* Create a hash table of big enough size to avoid collision.
Although hash definition is capable enough to handle collision.
Still we are taking bigger size hash to control hash table load ratio.
*/
HashingDoubleHashing hash_table (ARRAY_MAX_VALUE, true);
for (int i = 0; i < ARRAY_MAX_SIZE; i++) {
if (hash_table.search_data (sum - arr[i])) {
cout << " value: " << arr[i] << " value: " << sum - arr[i] << " Sum: " << sum << endl;
} else {
hash_table.insert_data (arr[i]);
}
}
}
int main ()
{
int arr[ARRAY_MAX_SIZE] = {0};
for (int i = 0; i < ARRAY_MAX_SIZE; i++) {
arr[i] = rand () % ARRAY_MAX_VALUE;
}
for (int i = 0; i < ARRAY_MAX_SIZE; i++) {
cout << arr[i] << " ";
if (i % 10 == 0 && i) {
cout << endl;
}
}
cout << endl;
int sum = 0;
cout << "Enter sum " << endl;
cin >> sum;
all_possible_combinations (arr, sum);
}
Let’s analyze the output of the above program.
83 86 77 15 93 35 86 92 49 21 62
27 90 59 63 26 40 26 72 36 11
68 67 29 82 30 62 23 67 35 29
2 22 58 69 67 93 56 11 42 29
73 21 19 84 37 98 24 15 70
Enter sum
143
value: 84 value: 59 Sum: 143
value: 70 value: 73 Sum: 143
