3
\$\begingroup\$

This is a problem that I had in mind for a loong time and today I decided to give it a go, the basic idea is you enter a number/sum and the program outputs all the possible ways this sum can be formed let's say we have 3 as input the output will be (1, 1, 1),(1, 2) I don't think that the code is really efficient so any tips are appreciated.

    static void Main(string[] args)
    {
        int sum = int.Parse(Console.ReadLine());
        List<List<int>> subsets = GetSubsets(sum);
        for (int i = 0; i < subsets.Count; i++)
        {
            Console.WriteLine(string.Join(",", subsets[i]));
        }
        Console.ReadKey();
    }

    private static List<List<int>> GetSubsets(int sum)
    {
        List<List<int>> subsets = new List<List<int>>();
        int[] allNumbers = new int[sum - 1];
        List<int> baseSubset = PopulateWith(1, allNumbers.Length + 1);
        int baseNumberIndex = 0;
        int additiveNumberIndex = 1;
        for (int i = 0; i < allNumbers.Length; i++)
        {
            allNumbers[i] = i + 1;
        }
        if (sum > 1)
        {
            // if 1 is entered as a sum we dont want to return 1 as result because that's not a sum of numbers it's just 1.
            subsets.Add(baseSubset);
        }
        while (baseNumberIndex < allNumbers.Length && additiveNumberIndex < allNumbers.Length)
        {
            List<int> currentSubset = PopulateWith(allNumbers[baseNumberIndex], (int)Math.Round((double)sum / allNumbers[baseNumberIndex]));
            int currentSum = currentSubset.Sum();
            while (true)
            {
                if (currentSum + allNumbers[additiveNumberIndex] > sum)
                {
                    currentSubset.Remove(allNumbers[baseNumberIndex]);
                }
                else
                {
                    currentSubset.Add(allNumbers[additiveNumberIndex]);
                }
                currentSum = currentSubset.Sum();
                if (currentSum == sum && !subsets.Any(seq => seq.SequenceEqual(currentSubset)))
                {
                    subsets.Add(currentSubset.ToList());
                }
                if (currentSum + allNumbers[additiveNumberIndex] > sum && !currentSubset.Contains(allNumbers[baseNumberIndex]))
                {
                    break;
                }
            }
            additiveNumberIndex++;
            if (additiveNumberIndex == allNumbers.Length)
            {
                baseNumberIndex++;
                additiveNumberIndex = baseNumberIndex + 1;
            }
        }
        return subsets;
    }

    private static List<int> PopulateWith(int number, int size)
    {
        List<int> collection = new List<int>();
        for (int i = 0; i < size; i++)
        {
            collection.Add(number);
        }
        return collection;
    }
\$\endgroup\$
7
  • \$\begingroup\$ "we have 3 as input the output will be (1, 1, 1),(1, 1, 2)" the second output is 4, did you mean (1, 2)? \$\endgroup\$ Oct 17 '16 at 22:45
  • \$\begingroup\$ @I'lladdcommentstomorrow Yes my bad .. \$\endgroup\$
    – Denis
    Oct 17 '16 at 22:50
  • \$\begingroup\$ For 3, would you also expect (2,1) and (3) as outputs? \$\endgroup\$ Oct 17 '16 at 23:02
  • \$\begingroup\$ But sum(3) is 3 - it should count. Do you really need an int[] allNumbers? It will just be additiveNumberIndex + 1. \$\endgroup\$
    – paparazzo
    Oct 18 '16 at 2:36
  • \$\begingroup\$ @Paparazzi You're right there is no point of having allNumbers, but I still don't agree that 3 is a sum. \$\endgroup\$
    – Denis
    Oct 18 '16 at 9:03
6
\$\begingroup\$

Rather than go through a line-by-line critique of your program, let me just say:

  • It is way too long and too complicated
  • You are getting hung up on all the adds and removes. This problem is much easier to solve if you never add or remove anything. Treat sequences as immutable data structures.

You should be able to do this in about four lines of code in your method body, and some little helper methods. Here's an example:

using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
    static IEnumerable<T> Singleton<T>(T t)
    {
        yield return t;
    }
    static IEnumerable<IEnumerable<int>> AllSums(int n, int min = 1)
    {
        for (int i = min; i <= n / 2; ++i)
            foreach(var seq in AllSums(n - i, i))
                yield return Singleton(i).Concat(seq);
        yield return Singleton(n);
    }
    public static void Main()
    {
        foreach(var result in AllSums(7))
            Console.WriteLine(string.Join(",", result));
    }
}

The key here is to make a clear specification for the AllSums method. It takes positive integers n and min and returns a sequence of sequences that all have the following properties:

  • They sum to n
  • The smallest number in the sequence is not smaller than min
  • The sequence is non-decreasing

Once you have a method that has these properties, the recursion becomes much easier to reason about.

Go through this implementation very carefully and annotate each line of code with its meaning and purpose in the algorithm.

For another application of this general principle of generating a sequence of data structures that all have a sum property, see my series of articles which begins here:

https://blogs.msdn.microsoft.com/ericlippert/2010/04/19/every-binary-tree-there-is/

\$\endgroup\$
3
  • \$\begingroup\$ I really like the design and shortness of code here but it works slower than mine. \$\endgroup\$
    – Denis
    Oct 19 '16 at 21:11
  • 1
    \$\begingroup\$ @denis: First, who cares? Do you have a user-focussed performance metric? Second, supposing we wished to performance optimize an algorithm; is it easier to optimize a four line algorithm or a 40 line algorithm? Third, your solution is not amenable to memoization optimizations. Look at the bigger picture here. You should be making the code right, and then elegant, and then fast. If you don't do it in that order you end up adding bugs when you try to optimize. \$\endgroup\$ Oct 19 '16 at 21:24
  • \$\begingroup\$ I see thank you a lot for the comment & the answer. \$\endgroup\$
    – Denis
    Oct 20 '16 at 8:14
-3
\$\begingroup\$

Recursively breaks the number down into pairs.

//test
foreach (List<int> li in BreakMeDown(7).Distinct())
    Debug.WriteLine(string.Join(", ", li));
//end test

This is getting close. It produces all the answers but it produces duplicates.

    public static IEnumerable<List<int>> BreakMeDown5(int n)
    {
        for (int i = 1, j = n - 1; i <= j; i++, j--)
        {
            List<int> breakMeDown = new List<int>();
            breakMeDown.Add(i);
            breakMeDown.Add(j);
            yield return breakMeDown;

            foreach (List<int> li in BreakMeDown5(i))
                yield return breakMeDown.Skip(1)
                                        .Concat(li)
                                        .ToList();

            if (i != j)
            {
                foreach (List<int> li in BreakMeDown5(j))
                    yield return breakMeDown.Take(1)
                                            .Concat(li)
                                            .ToList();
            }
        }
    }
\$\endgroup\$
6
  • \$\begingroup\$ DVs it produces the answer and is super fast. \$\endgroup\$
    – paparazzo
    Jul 24 '17 at 10:54
  • 1
    \$\begingroup\$ it produces the answer and is super fast this doesn't matter. This is Code Review and not suggest-an-alternative-version. You post a lot of solutions but without reviewing the code. This is not the purpose of this site. You don't even write why your code is faster. You never explain what you did. \$\endgroup\$
    – t3chb0t
    Jul 24 '17 at 10:58
  • \$\begingroup\$ @t3chb0t See accepted answer. Question "I don't think that the code is really efficient so any tips are appreciated." \$\endgroup\$
    – paparazzo
    Jul 24 '17 at 10:59
  • \$\begingroup\$ This is Eric, he gets 5k upvotes for just posting an answer, it's a completely different category. \$\endgroup\$
    – t3chb0t
    Jul 24 '17 at 11:00
  • \$\begingroup\$ any tips are appreciated - where is your answer giving any tips? \$\endgroup\$
    – t3chb0t
    Jul 24 '17 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.