Subset - Sum Problem with Integer Arrays

munagalasantosh

Rate me:

3.20/5 (3 votes)

16 Apr 2014CPOL

16.4K

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:

0,2,3
1,2,3
2,3
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();

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Written By

munagalasantosh

Software Developer (Senior)

India

This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ca1 { class Program { static List<PartialList> allSolutions = new List<PartialList>(); class Element { public int Value { get; set; } public int Index { get; set; } public Element(int value, int index) { Value = value; Index = index; } public override string ToString() { return Value.ToString(); } } class PartialList { public List<Element> List = new List<Element>(); int sum = 0; StringBuilder sb = new StringBuilder(); public int Add(Element el) { if (List == null) List = new List<Element>(); List.Add(el); sum += el.Value; if (sb.Length > 0) sb.Append(","); sb.Append(el.Value.ToString()); return sum; } public int Sum() { return sum; } public string GetIndexes() { StringBuilder sb = new StringBuilder(); foreach (Element el in List) { if (sb.Length > 0) sb.Append(","); sb.Append(el.Index.ToString()); } return sb.ToString(); } public PartialList Clone() { PartialList newList = new PartialList(); foreach (Element el in List) newList.Add(el); return newList; } public override string ToString() { return sb.ToString(); } } static void Main(string[] args) { // Initialization PartialList startList = new PartialList(); startList.Add(new Element(1, 0)); startList.Add(new Element(2, 1)); startList.Add(new Element(4, 2)); startList.Add(new Element(6, 3)); // Building list // A single element is a part of the solution or is not. foreach (Element element in startList.List) { int listLenght = allSolutions.Count; // add element to all existing solutions for (int i = 0; i<listLenght; i++) { PartialList newList = allSolutions[i].Clone(); newList.Add(element); allSolutions.Add(newList); } // add element as start of new series PartialList newList2 = new PartialList(); newList2.Add(element); allSolutions.Add(newList2); } // Writing out solution foreach (PartialList item in allSolutions) { if (item.Sum() >= 10) Console.WriteLine(item.GetIndexes()); } Console.ReadLine(); // Writing out all combinations foreach (PartialList item in allSolutions) { Console.WriteLine(item.GetIndexes()); } Console.ReadLine(); } } }

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Subset - Sum Problem with Integer Arrays

Introduction

Using the Code

License

Comments and Discussions