Assignment:

Write a program to display all possible permutations of additions that lead to the Input number so long as they contain the digit "1"

Example:

Input: 5

Output:

1 1 1 2
1 1 2 1
1 2 1 1
2 1 1 1

1 1 3
1 3 1
3 1 1

1 4
4 1

My solution:

Code:
#include <iostream>
#include <iomanip>

int main (void)
{
    int Input , Ctr1 , Ctr2 , Ctr3;

    std::cin >> Input;

    int* Sum = new int[Input - 1];

    int Num = 1;

    for ( Ctr1 = 0 ; Ctr1 < Input - 1 ; Ctr1++ ) Sum[Ctr1] = 1;

    for ( Ctr1 = 0 ; Ctr1 < Input - 2 ; Ctr1++ )
    {
        std::cout << std::endl;

        for ( Ctr2 = Ctr1 + 1 ; Ctr2 < Input ; Ctr2++ )
        {
            Sum[Input - (Ctr2 + 1)] += Num;

            for ( Ctr3 = 0 ; Ctr3 < Input - (Ctr1 + 1) ; Ctr3++ )
                std::cout << std::setw(3) << Sum[Ctr3];

            std::cout << std::endl;

            Sum[Input - (Ctr2 + 1)] -= Num;
        }

        Num++;
    }

    std::cin.get();

    delete[] Sum;

    return 0;
}
This works fine and produces the desired output. However, I do think there might be better ways to do this... As reasoned in one of my old threads by a site mod, for a large Input number, I'd be declaring a really large array which is bad.
Could someone suggest an alternate/better approach?

Thanks!