Print all subsets that sum up to specific value

Question

I've being trying for some time now to find all the elements ^{(including non-consecutive)} of an array that sum up to specific value:

using System;

namespace ProgrammingBasics 
{
    class Exercise
    {
        static void Main()
        {
            PrintArray(arr);
            SubarrayWithSum();
        }
        //--------------------------------------------------------------------

        /*
            Data members.

        */
        // targer array
        static int[] arr = { 2, 1, 2, 4, 3, 5, 2, 6 };
        // target sum
        static int sum = 14;

        //--------------------------------------------------------------------

        /*
            Method: IsSubarrayWithSum(arr, sum);

            It returns a bool value that indicates
            whether there is a subarray within arr
            with elements that sum up to specific value.
        */
        static void SubarrayWithSum()
        {
            int depth = 0;
            int startIndex = 0;
            int endIndex = 1;

            CheckAllCombinations(new int[arr.Length], startIndex, endIndex, depth);
        }
        //--------------------------------------------------------------------

        /*
            Method: CheckAllCombinations(subarray, sum);

        */
        static void CheckAllCombinations(int[] subarray, int startIndex, int endIndex, int depth)
        {
            if (depth >= arr.Length)
            {
                return;
            }
            //Console.ReadKey();
            for (int i = startIndex; i < endIndex; i++)
            {
                subarray[i] = arr[i];
                //Console.WriteLine("startIndex = {0}, depth = {1}, i = {2}", startIndex, depth, i);
                if (IsWantedSum(subarray))
                {
                    Console.Write("S = {0} -> yes", sum);
                    PrintSubArray(subarray);
                }
                //PrintArray(subarray);
                //Console.ReadKey();
                CheckAllCombinations(new int [arr.Length], startIndex += 1, endIndex = (endIndex < arr.Length)? endIndex + 1 : endIndex, depth += 1);
            }
        }
        //--------------------------------------------------------------------

        /*
            Method: IsWantedSum(int[] arr)

        */
        static bool IsWantedSum(int[] arr)
        {
            int currentSum = 0;

            for (int i = 0; i < arr.Length; i++)
            { 
                currentSum += arr[i];
            }

            if (currentSum == sum)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        //--------------------------------------------------------------------
        /*
            Method: PrintArray();

        */
        static void PrintArray(int[] subarray)
        {
            Console.Write("{");
            for (int i = 0; i < subarray.Length; i++)
            {
                Console.Write(subarray[i]);
                if (i < subarray.Length -1) Console.Write(", ");
            }
            Console.WriteLine("}");
        }

        //--------------------------------------------------------------------
        /*
            Method: PrintSubArray();

        */
        static void PrintSubArray(int[] subarray)
        {
            Console.Write("(");
            for (int i = 0; i < subarray.Length; i++)
            {
                if (subarray[i] != 0)Console.Write(subarray[i]);
                if (subarray[i] != 0 && i < subarray.Length - 1) Console.Write(" + ");
            }
            Console.WriteLine(" = {0})", sum);
        }
    }
}

I'm getting somewhat partially right result:

{2, 1, 2, 4, 3, 5, 2, 6}
S = 14 -> yes(4 + 3 + 5 + 2 + = 14)
S = 14 -> yes(2 + 4 + 3 + 5 + = 14)
S = 14 -> yes(4 + 3 + 5 + 2 + = 14)
S = 14 -> yes(4 + 3 + 5 + 2 + = 14)
S = 14 -> yes(2 + 4 + 3 + 5 + = 14)
S = 14 -> yes(4 + 3 + 5 + 2 + = 14)

with duplications and missing sub-arrays of non-consecutive elements such as:

yes (1 + 2 + 5 + 6 = 14)

Could someone give me a hint on the problems of my algorithm and probably suggest a correction / new implementation?

Your program doesn't seem to ever check non-consecutive subarrays. — n. m. could be an AI, Aug 22 '16 at 15:56
My intuition would be to sort your list and then to apply recursively find on list[1]..list[n] the sum = sum - list[0], having a guard on your sum 14 as it cannot be a sum of more than 14 terms — LeBaptiste, Aug 22 '16 at 16:05

score 1 · Answer 1 · edited May 23 '17 at 12:14

Here's a simple way to do it with combinations. There's probably a better way to store them (I'm thinking using a dictionary to encode all the sub sums you already have). At the end of the day, if you want to account for non-consecutive elements, you're going to have to get the sub arrays that are possible in this case, and not just look at consecutive choices. Credit for the combination algorithm goes to ojlovecd here .

    class Exercise
    {
        static void Main()
        {
            PrintArray(arr);
            // SubarrayWithSum();


            var result = GetCombination(arr);

            foreach(var list in result)
            {
                var total = list.Sum();
                if (total == sum)
                    PrintArray(list);
            }
        }
        static List<int> arr = new List<int> { 2, 1, 2, 4, 3, 5, 2, 6 };
        static int sum = 14;

        static List<List<int>> GetCombination(List<int> list)
        {
            var result = new List<List<int>>();
            result.Add(new List<int>());
            double count = Math.Pow(2, list.Count);
            for (int i = 1; i <= count - 1; i++)
            {
                string str = Convert.ToString(i, 2).PadLeft(list.Count, '0');
                for (int j = 0; j < str.Length; j++)
                {
                    if (str[j] == '1')
                    {
                        result[i - 1].Add(list[j]);
                    }
                }
                result.Add(new List<int>());
            }
            return result;
        }

        static void PrintArray(List<int> subarray)
        {
            Console.Write("{");
            for (int i = 0; i < subarray.Count; i++)
            {
                Console.Write(subarray[i]);
                if (i < subarray.Count - 1) Console.Write(", ");
            }
            Console.WriteLine("}");
        }
    }

jdweng · Answer 2 · 2016-08-25T00:28:00.840

I think the duplicates are occurring because you have zeroes in the array that you are adding. See updated code which runs quicker.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace ProgrammingBasics
{
    class Exercise
    {
        static void Main()
        {
            PrintArray(arr);
            SubarrayWithSum();
        }
        //--------------------------------------------------------------------

        /*
            Data members.

        */
        // targer array
        static int[] arr = { 2, 1, 2, 4, 3, 5, 2, 6 };
        // target sum
        static int sum = 14;

        //--------------------------------------------------------------------

        /*
            Method: IsSubarrayWithSum(arr, sum);

            It returns a bool value that indicates
            whether there is a subarray within arr
            with elements that sum up to specific value.
        */
        static void SubarrayWithSum()
        {
            int depth = 0;
            int endIndex = arr.Length - 1;

            CheckAllCombinations(new int[arr.Length], depth);
        }
        //--------------------------------------------------------------------

        /*
            Method: CheckAllCombinations(subarray, sum);

        */
        static void CheckAllCombinations(int[] subarray, int depth)
        {
            //Console.ReadKey();
            for (int i = depth; i < arr.Length; i++)
            {
                subarray[depth] = arr[i];
                Console.WriteLine("depth = {0}, i = {1}, array = '{2}'  ", depth, i, string.Join(",", subarray.Select(x => x.ToString()).ToArray()));
                int currentSum = subarray.Take(depth + 1).Sum();
                if (currentSum == sum)
                {
                    Console.Write("S = {0} -> yes : ", sum);
                    Console.WriteLine(string.Join(",", subarray.Take(depth + 1)));
                }
                //PrintArray(subarray);
                //Console.ReadKey();
                if (currentSum < sum)
                {
                    CheckAllCombinations(subarray, depth + 1);
                }
            }
        }
        //--------------------------------------------------------------------

        /*
            Method: IsWantedSum(int[] arr)

        */

        //--------------------------------------------------------------------
        /*
            Method: PrintArray();

        */
        static void PrintArray(int[] subarray)
        {
            Console.Write("{");
            for (int i = 0; i < subarray.Length; i++)
            {
                Console.Write(subarray[i]);
                if (i < subarray.Length - 1) Console.Write(", ");
            }
            Console.WriteLine("}");
        }

        //--------------------------------------------------------------------
        /*
            Method: PrintSubArray();

        */
        static void PrintSubArray(int[] subarray)
        {
            Console.Write("(");
            for (int i = 0; i < subarray.Length; i++)
            {
                if (subarray[i] != 0) Console.Write(subarray[i]);
                if (subarray[i] != 0 && i < subarray.Length - 1) Console.Write(" + ");
            }
            Console.WriteLine(" = {0})", sum);
        }
    }
}

Make sure you have latest change where I changed from 'i += 1' to 'i = 1' — jdweng, Aug 22 '16 at 17:46
I ran your code, but it also seems to only find consecutive options. — Kolichikov, Aug 24 '16 at 22:19
The was one minor error From : CheckAllCombinations(subarray, i + 1); To : CheckAllCombinations(subarray, depth + 1); — jdweng, Aug 25 '16 at 00:28
Having run that, the output seems a little weird/wrong, most of the entries are just S = 14 -> yes { 6 + 6 + 2 + 6 + 6 + 6 + 6 + 6+ =14}. There are so many entries that it makes it impossible to find the useful ones in the incorrect ones. — Kolichikov, Aug 25 '16 at 01:06
I left the debug code that writes all the tries in the code. There is no need to clear the array after each try. The depth variable indicates how many items in the array are used. The outputs with 'yes' are the rows that add up to 14. — jdweng, Aug 25 '16 at 08:15
Buy that line I posted clearly doesn't add up to 14, it doesn't even exist as a potential combination. — Kolichikov, Aug 25 '16 at 15:30
In fact, having run through the algorithm again, yours finds just one possible answer, and every single other option is incorrect. You are going through recursively,but when you loop `for (int i = depth; i < arr.Length; i++)`, you guarantee that as you go forward, you'll collect the last elements in the entire array (as your recursion pops up a level, since you don't break your iterations when target is exceeded, you'll just populate the last array positions (i > depth) with the last element of the sample array. The original was incomplete, but this answer is just wrong. — Kolichikov, Aug 25 '16 at 16:09
Kolichikov : The code is correct, your answer is totally wrong. You don't understand my code. There is nothing wrong with going to last element. — jdweng, Aug 25 '16 at 16:29
If you can explain how the printout I provided from your code is a valid combination, I'll agree with you. But copy and pasting your code provided 1 of the 19 possible combinations, and a bunch of just incorrect ones. Try to run your code and actually look at the results. — Kolichikov, Aug 25 '16 at 16:46
The yes lines are correct. The line before if you use DEPTH + 1 as the array size it show the same array as the YES line. So all the debug code you should only look at Depth + 1. It was inefficient to keep on clearing the array. — jdweng, Aug 25 '16 at 17:58

score 0 · Accepted Answer · answered Aug 24 '16 at 10:54

OK, here is small attempt to briefly describe the info that I went through to understand the problem¹ and implement a basic solution.

It turns out that The Subset Sum Problem is considered a special case of the Knapsack Problem in which we are searching to maximize profit while keeping value called weight under specific capacity, but in our case the profit and weight associated with each value are identical.

There are variety of great solutions described in "Knapsack Problems" - Keller, Pferschy, Pisinger, however, for the time being the simplest solution that I could implement and understand, not carrying about complexity and / or efficacy, looks like this:

    //--------------------------------------------------------------------

    /*
        Method: FindSubArray();

        Base case: - if current sum == targer sum: print current elements.
                   - if index == arr.Length: terminate search.

        Recursive step: 
                   - do not/select element with index and do not/update the current sum; recursive call with updated current sum and index.
    */
    static void FindSubArray(int index, int currentSum, bool[] subArray)
    {
        // base case
        if (currentSum == targetSum)
        {
            PrintSubArray(subArray);
        }
        else if (index == arr.Length)
        {
            return;
        }
        else
        {
            // recursive calls
            subArray[index] = true;
            currentSum += arr[index];
            FindSubArray(index + 1, currentSum, subArray);

            currentSum -= arr[index]; // restore previous value of the sum signifying: element not selected
            subArray[index] = false;
            FindSubArray(index + 1, currentSum, subArray);
        }
    }

where PrintSubArray(subArray); prints all the elements of arr marked with true in subArray.

Output:

{2, 1, 2, 4, 3, 5, 2, 6}
S = 14 -> yes (2 + 1 + 2 + 4 + 3 + 2 + = 14)
S = 14 -> yes (2 + 1 + 2 + 4 + 5 + = 14)
S = 14 -> yes (2 + 1 + 2 + 3 + 6 = 14)
S = 14 -> yes (2 + 1 + 4 + 5 + 2 + = 14)
S = 14 -> yes (2 + 1 + 3 + 2 + 6 = 14)
S = 14 -> yes (2 + 1 + 5 + 6 = 14)
S = 14 -> yes (2 + 2 + 4 + 6 = 14)
S = 14 -> yes (2 + 2 + 3 + 5 + 2 + = 14)
S = 14 -> yes (2 + 4 + 3 + 5 + = 14)
S = 14 -> yes (2 + 4 + 2 + 6 = 14)
S = 14 -> yes (1 + 2 + 4 + 5 + 2 + = 14)
S = 14 -> yes (1 + 2 + 3 + 2 + 6 = 14)
S = 14 -> yes (1 + 2 + 5 + 6 = 14)
S = 14 -> yes (1 + 4 + 3 + 6 = 14)
S = 14 -> yes (1 + 5 + 2 + 6 = 14)
S = 14 -> yes (2 + 4 + 3 + 5 + = 14)
S = 14 -> yes (2 + 4 + 2 + 6 = 14)
S = 14 -> yes (4 + 3 + 5 + 2 + = 14)
S = 14 -> yes (3 + 5 + 6 = 14)

The book that I'm reading states the problem simply as: "Find if there is a sub array with elements that sum up to specific value'.

By (searching) going through all the possible combinations (sums) of the array elements. — Ziezi, Dec 04 '18 at 04:23

Print all subsets that sum up to specific value

3 Answers3