Given a number N, write a method that displays all possible combinations of numbers that add up to N, as lists. (Exclude the N+0=N).For example, if N=4, display: {1,1,1,1} {2,1,1} {2, 2} {3, 1} {4}
void SummationCombinations(int n)
{
SummationCombinationsHelper(n, 0);
}
void SummationCombinationsHelper(int n, int index)
{
// Static member - this line will be executed only once
static int *arr = new int[n];
if (n <= 0)
{
Display(arr, index);
return;
}
for (int i = 1; i <= n; i++)
{
arr[index] = i;
// Avoid repeating the same numbers in different positions
if (index != 0 && arr[index - 1] < arr[index])
return;
SummationCombinationsHelper(n - i, index + 1);
}
}
void Display(int *arr, int size)
{
cout << "{";
for (int i = 0; i < size; i++)
{
cout << arr[i];
if (i < size - 1)
cout << ", ";
}
cout << "}" << endl;
}
|
|