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));
}

CodePudding user response：

static void findCombinationsUtil(int []arr, int index,
                                 int num, int reducedNum)
{

    if (reducedNum < 0)
        return;
 
    if (reducedNum == 0)
    {
        for (int i = 0; i < index; i  )
            Console.Write (arr[i]   " ");
            Console.WriteLine();
        return;
    }
 
  
    int prev = (index == 0) ?
                          1 : arr[index - 1];
 
    for (int k = prev; k <= num ; k  )
    {
        
        arr[index] = k;
 
      
        findCombinationsUtil(arr, index   1, num,
                                 reducedNum - k);
    }
}
 

static void findCombinations(int n)
{
 
    int []arr = new int [n];
 
    findCombinationsUtil(arr, 0, n, n);
}
 

static public void Main ()
{
    int n = 5;
    findCombinations(n);
}
}

CodePudding user response：

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);

            Console.WriteLine(string.Join("\n", combinationList));

            Console.ReadLine();
          
        }
        static void GenerateCombinations(List<int> numbers, int sum)
        {
            for (int i = 1; i <= SUM; i  )
            {
                int newSum = sum   i;
                
                if (newSum > SUM) break;
                
                List<int> newList = new List<int>(numbers);
                newList.Add(i);

                if (newSum == SUM)
                {
                    combinationList.Add(string.Join("   ", newList));
                    break;
                }
                else
                {
                    GenerateCombinations(newList, newSum);
                }

            }
        }
    }