12,552,576 members (59,133 online)
alternative version

7.4K views
1 bookmarked
Posted

Subset - Sum Problem with Integer Arrays

, 16 Apr 2014 CPOL
 Rate this:
Get all the array index where the sum equals or is greater than some x value

Introduction

Here, we are going to solve the Subset-sum problem using integer Array set. Subset problem is a complex problem. We have to find a set of integers where its sum is equal to or greater than some x value.

For example: Assume there is a integer `array int[] arrvalue = { 1, 2, 4, 6 }; `our problem is to find all the subsets where it sum is `>= 10`. and set of index's should be unique.

The result should be:

1. 0,2,3
2. 1,2,3
3. 2,3
4. 0,1,2,3

Using the Code

```int[] arrvalue = { 1, 2, 4, 6 };

List<string> lst = new List<string>();

for (int x = 0; x < arrvalue.Count(); x++)
{
string data1 = string.Empty;
data1 = x.ToString();
for (int i = x + 1; i < arrvalue.Count(); i++)
{
string data = string.Empty;

data = data1 + "," + i.ToString();

//data = string.Empty;
for (int j = i; j < arrvalue.Count(); j++)
{
if (!data.Contains(j.ToString()))
{
data = data + "," + j;
}
}
}
}

List<string> finallist = new List<string>();
foreach (string stritem in lst)
{
string[] strsplit = stritem.Split(',');

int result = 0;

foreach (string str in strsplit)
{
result = result + arrvalue[Convert.ToInt32(str)];
}

if (result >= 10)
{
}
}

foreach (string  strresult in finallist)
{
Console.WriteLine(strresult);
}

Share

 Software Developer (Senior) India
No Biography provided

You may also be interested in...

 First Prev Next
 My vote of 2 LostTheMarbles22-Apr-14 4:31 LostTheMarbles 22-Apr-14 4:31
 A string isn't an appropriate data structure to store a list of integers John Brett17-Apr-14 3:09 John Brett 17-Apr-14 3:09
 Solving more than 4 elements in array Member 981169416-Apr-14 22:02 Member 9811694 16-Apr-14 22:02
 Last Visit: 31-Dec-99 18:00     Last Update: 24-Oct-16 14:06 Refresh 1