Click here to Skip to main content
11,489,693 members (67,340 online)
Click here to Skip to main content

Subset - Sum Problem with Integer Arrays

, 16 Apr 2014 CPOL 4.5K 1
Rate this:
Please Sign up or sign in to vote.
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();
                
                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)

Share

About the Author

munagalasantosh
Software Developer (Senior)
India India
No Biography provided

Comments and Discussions

 
GeneralMy vote of 2 Pin
LostTheMarbles22-Apr-14 5:31
professionalLostTheMarbles22-Apr-14 5:31 
GeneralA string isn't an appropriate data structure to store a list of integers Pin
John Brett17-Apr-14 4:09
memberJohn Brett17-Apr-14 4:09 
SuggestionSolving more than 4 elements in array [modified] Pin
Member 981169416-Apr-14 23:02
memberMember 981169416-Apr-14 23:02 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

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

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150520.1 | Last Updated 16 Apr 2014
Article Copyright 2014 by munagalasantosh
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid