I've been struggling with this pretty tricky problem for the past week :( I have to find all combinations of numbers that sum up to a given natural number using recursion. I'm not allowed to use LINQ or anything else besides "using system"
For example if the input is 7 then the output should look like this:
1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1 + 1
2 + 2 + 2 + 1
3 + 1 + 1 + 1 + 1
3 + 2 + 1 + 1
3 + 2 + 2
3 + 3 + 1
4 + 1 + 1 + 1
4 + 2 + 1
4 + 3
5 + 1 + 1
5 + 2
6 + 1
The numbers from the combination should be listed exactly in that order so for an input of 3 for example the output should be exactly as follows:
1 + 1 + 1
2 + 1
For an input of 4 the output should look like this:
1 + 1 + 1 + 1
2 + 1 + 1
2 + 2
3 + 1
For every new list of combinations we increment the first number in the list and then we continue with the remaining part of the previous list until the sum will be equal with the input.
Just positive numbers are allowed between 1 (1 included) and input - 1.
My code so far gives me the following output for the same given input of 7:
+ 1
+ 1 + 1 + 2
+ 1 + 1 + 1
+ 2 + 2 + 3
+ 1 + 1 + 1
+ 1 + 1 + 2
+ 2 + 1
+ 1 + 1 + 2
+ 2 + 2 + 1
+ 3 + 3 + 4
+ 1 + 1 + 1
+ 1 + 1 + 2
+ 1 + 1 + 1
+ 2 + 2 + 3
+ 2 + 1
+ 1 + 1 + 2
+ 1 + 1 + 1
+ 2 + 2 + 3
...
Can you please help me with some suggestions?
static string GenerateCombinations(int n)
{
string combinationList = "";
for (int index = 1; index < n - 1; index++)
{
string intermediaryList = GenerateCombinations(n - index, index) + " + " + index;
combinationList += intermediaryList;
}
return combinationList + "\n";
}
static string GenerateCombinations(int n, int index)
{
string combinationList = "";
for (int i = 1; i < n - 1; i++)
{
if (i <= index)
{
string intermediaryList = GenerateCombinations(n) + " + " + index;
combinationList += intermediaryList;
}
}
return combinationList;
}
static void Main()
{
int n = Convert.ToInt32(Console.ReadLine());
Console.WriteLine(GenerateCombinations(n));
}
Try following :
class Program
{
static List<string> combinationList = new List<string>();
const int SUM = 7;
static void Main(string[] args)
{
List<int> numbers = new List<int>();
GenerateCombinations(numbers, 0);
combinationList.Sort();
Console.WriteLine(string.Join("\n", combinationList));
Console.ReadLine();
}
static void GenerateCombinations(List<int> numbers, int sum)
{
int start = 1;
if (numbers.Count > 0) start = numbers[0];
for (int i = start; i <= SUM; i++)
{
int newSum = sum + i;
if (newSum > SUM) break;
List<int> newList = new List<int>(numbers);
newList.Insert(0,i);
if (newSum == SUM)
{
combinationList.Add(string.Join(" + ", newList));
break;
}
else
{
GenerateCombinations(newList, newSum);
}
}
}
}
Since you are looking for a recursive solution, let's do it recursively without Linq and other mean.
Let's start from the basic: when given 0, we have an empty solution:
private static int[][] Solutions(int value) {
if (value <= 0)
return new int[][] { new int[0] };
//TODO: other cases for 1, 2, ...
}
Time to do the next step: if we know how to solve for some n - 1 (n - 1 >= 0) we can solve for n as follow:
all solutions start from m (m < n) are in form
`m + solutions for n - m which uses m .. 1 only`
E.g.
6 + 1 <- starts from 6, solves for 7 - 6 = 1, uses 6..1 only
5 + 2 ...
5 + 1 + 1
4 + 3
4 + 2 + 1
4 + 1 + 1 + 1 ...
3 + 3 + 1 <- starts from 3, solves for 7 - 3 = 4, uses 3..1 only
3 + 2 + 2 <- starts from 3, solves for 7 - 3 = 4, uses 3..1 only
3 + 2 + 1 + 1 <- starts from 3, solves for 7 - 3 = 4, uses 3..1 only
3 + 1 + 1 + 1 + 1 ...
2 + 2 + 2 + 1
2 + 2 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1 ...
1 + 1 + 1 + 1 + 1 + 1 + 1 <- starts from 1, solves for 7 - 1 = 6, uses 1..1 only
This recursion can be encoded as
private static int[][] Solutions(int value, int startWith = -1) {
if (value <= 0)
return new int[][] { new int[0] };
if (startWith < 0)
startWith = value - 1;
List<int[]> solutions = new List<int[]>();
for (int i = Math.Min(value, startWith); i >= 1; --i)
foreach (int[] solution in Solutions(value - i, i)) {
int[] next = new int[solution.Length + 1];
Array.Copy(solution, 0, next, 1, solution.Length);
next[0] = i;
solutions.Add(next);
}
// Or just (if we are allow a bit of Linq)
// return solutions.ToArray();
int[][] answer = new int[solutions.Count][];
for (int i = 0; i < solutions.Count; ++i)
answer[i] = solutions[i];
return answer;
}
Demo
var result = Solutions(7);
// A pinch of Linq for demonstration
string report = string.Join(Environment.NewLine, result
.Select(solution => string.Join(" + ", solution)));
Console.Write(report);
Outcome:
6 + 1
5 + 2
5 + 1 + 1
4 + 3
4 + 2 + 1
4 + 1 + 1 + 1
3 + 3 + 1
3 + 2 + 2
3 + 2 + 1 + 1
3 + 1 + 1 + 1 + 1
2 + 2 + 2 + 1
2 + 2 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1
Here is a solution not using collections (only using System;) and generating the output in the required order.
public static void PrintCombinations(int n)
{
PrintRest("", 0, n, n - 1);
}
private static void PrintRest(string listStart, int startSum, int n, int max)
{
for (int i = 1; i <= max; i++) {
string list = listStart.Length > 0
? listStart + " + " + i.ToString()
: i.ToString();
int sum = startSum + i;
if (sum == n) {
Console.WriteLine(list);
} else if (sum < n) {
PrintRest(list, sum, n, i);
}
}
}
You would call it as
PrintCombinations(7);
It starts by taking all possible start summands and calling itself to construct the rest of the sum. The combinations up to the current point are passed as string parameter listStart. The sum it represents is passed as int startSum. The target sum is n. max is the biggest summand allowed.