In this post I am going to explain how to implement an algorithm for the subset sum problem. This task is often encountered in competitions and in areas of computer science such as cryptography(it may also be applicable to job interviews). Just to make things clear, I am using Microsoft Visual Studio 2012 Express edition and this will be a C# console application.
Problem introduction
The primary nature of the problem is the following: given a set of integers, your task is to check if there is a subset whose sum equals to zero. For example given this set of numbers {-2, 4, -2, 5, -1}, how many subsets are there to have a sum of 0? We have {-2, -2, 4} and {-2, -2, -1, 5}. The algorithm I am about to show you though will work for any sum which makes it also appropriate for the Knapsack problem .
About the algorithm
The algorithm to solve the task is NP-complete. That means we need to check the sum of every combination of integers in the set. The number of checks for n given integers is 2n - 1.
The Implementation
The algorithm is somehow a bit odd so I will explain how it works while simultaneously posting chunks of code. So lets begin with the trivial stuff. First off we have to declare the variables, one to hold the number of the found subsets - a counter, one for holding the required sum and a variable for the size of the whole starting set - n. After that we need to enter the actual numbers. I am using an array data structure to hold them.
using System;
class SubsetSums
{
static void Main(string[] args)
{
int counter = 0;
int sum;
int n;
// Taking input data
Console.Write("Enter sum: ");
sum = int.Parse(Console.ReadLine());
Console.Write("How many numbers: ");
n = int.Parse(Console.ReadLine());
int[] set = new int[n];
for(int i = 0; i < n; i++)
{
Console.Write("Enter a number: ");
set[i] = int.Parse(Console.ReadLine());
}
}
}As I have pointed out earlier, the number of possible combinations with the integers from the set is 2n - 1. So now we will create a loop that will go through every combination. Inside of it there is going to be a string variable which will serve us as a bit mask.
using System;
class SubsetSums
{
static void Main(string[] args)
{
int counter = 0;
int sum;
int n;
// Taking input data
Console.Write("Enter sum: ");
sum = int.Parse(Console.ReadLine());
Console.Write("How many numbers: ");
n = int.Parse(Console.ReadLine());
int[] set = new int[n];
for(int i = 0; i < n; i++)
{
Console.Write("Enter a number: ");
set[i] = int.Parse(Console.ReadLine());
}
int checks = (int)Math.Pow(2, n);
for(int i = 1; i < checks; i++)
{
string mask = Convert.ToString(i, 2).PadLeft(n, '0');
}
}
}Say that we have the given set: {-2, 4, -2, 5, -1} and lets assume that the for-loop has iterated to the point when i = 3. The mask then is going to have the following value: "00011". This means that in the current combination we will use integers from the set which correspond to the bits-1 in the mask, thus 5 and -1. Just like a light switch we turn the numbers on and off. And now we just need to calculate the sum of those integers in the combination.
using System;
class SubsetSums
{
static void Main(string[] args)
{
int counter = 0;
int sum;
int n;
// Taking input data
Console.Write("Enter sum: ");
sum = int.Parse(Console.ReadLine());
Console.Write("How many numbers: ");
n = int.Parse(Console.ReadLine());
int[] set = new int[n];
for(int i = 0; i < n; i++)
{
Console.Write("Enter a number: ");
set[i] = int.Parse(Console.ReadLine());
}
int checks = (int)Math.Pow(2, n);
for(int i = 1; i < checks; i++)
{
string mask = Convert.ToString(i, 2).PadLeft(n, '0');
int combinationSum = 0;
for(int j = 0; j < n; j++)
{
int charValue = Convert.ToInt32(char.GetNumericValue(mask[j]));
combinationSum += charValue * set[j];
}
}
}
}Now we just have to check if the combination sum equals the given sum. If this is true, we will iterate the counter variable and print the numbers from this subset.
using System;
class SubsetSums
{
static void Main(string[] args)
{
int counter = 0;
int sum;
int n;
// Taking input data
Console.Write("Enter sum: ");
sum = int.Parse(Console.ReadLine());
Console.Write("How many numbers: ");
n = int.Parse(Console.ReadLine());
int[] set = new int[n];
for(int i = 0; i < n; i++)
{
Console.Write("Enter a number: ");
set[i] = int.Parse(Console.ReadLine());
}
int checks = (int)Math.Pow(2, n);
for(int i = 1; i < checks; i++)
{
string mask = Convert.ToString(i, 2).PadLeft(n, '0');
int combinationSum = 0;
for(int j = 0; j < n; j++)
{
int charValue = Convert.ToInt32(char.GetNumericValue(mask[j]));
combinationSum += charValue * set[j];
}
if(sum == combinationSum)
{
for(int j = 0; j < n; j++)
{
int charValue = Convert.ToInt32(char.GetNumericValue(mask[j]));
if(charValue != 0)
{
Console.Write("{0} ", charValue * set[j]);
}
counter++;
Console.WriteLine();
}
}
}
Console.WriteLine(counter);
}
}And that's it!