Subset - Sum Problem with Integer Arrays

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();
                
                lst.Add(data);
                //data = string.Empty;
                for (int j = i; j < arrvalue.Count(); j++)
                {
                    if (!data.Contains(j.ToString()))
                    {
                        data = data + "," + j;
                        lst.Add(data);
                    }
                }
            }
        }
        
        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)
            {
                finallist.Add(stritem);
            }
        }
        
        foreach (string  strresult in finallist)
        {
            Console.WriteLine(strresult);
        }
        
        Console.ReadLine();