#include <stdio.h>

void findWays(int steps[], int n, int index) {
    if (n == 0) {
        for (int i = 0; i < index; i++) 
            printf("%d ", steps[i]);
        printf("\n");
        return;
    }
    if (n < 0) return;

    steps[index] = 1;
    findWays(steps, n - 1, index + 1);

    steps[index] = 2;
    findWays(steps, n - 2, index + 1);
}

int main() {
    int n = 4;  // Change this to the desired number of steps
    int steps[n];  // Array to store current steps combination
    findWays(steps, n, 0);
    return 0;
}

/*findWays Function:

This recursive function finds all possible ways to climb n steps.
It takes an array steps to store the current combination of steps, n as the number of steps left, 
and index as the current position in the steps array.
If n becomes 0, it means a valid combination of steps has been found, so it prints the combination.
If n becomes negative, it returns because the current combination is not valid.
It tries to take a 1-step and recursively calls itself.
It tries to take a 2-step and recursively calls itself.
main Function:

Sets the total number of steps n.
Initializes an array steps to store the steps in the current combination.
Calls the findWays function to find and print all possible ways to climb the staircase.
This code is simple, demonstrates basic backtracking, and prints all combinations of steps to climb a staircase of a given height.
    

n=3
findWays(steps, 3, 0)
|
|-- steps[0] = 1, findWays(steps, 2, 1)
|   |
|   |-- steps[1] = 1, findWays(steps, 1, 2)
|   |   |
|   |   |-- steps[2] = 1, findWays(steps, 0, 3) --> "1 1 1"
|   |
|   |-- steps[1] = 2, findWays(steps, 0, 2) --> "1 2"
|
|-- steps[0] = 2, findWays(steps, 1, 1)
    |
    |-- steps[1] = 1, findWays(steps, 0, 2) --> "2 1"

n=4

findWays(steps, 4, 0)
|
|-- steps[0] = 1, findWays(steps, 3, 1)
|   |
|   |-- steps[1] = 1, findWays(steps, 2, 2)
|   |   |
|   |   |-- steps[2] = 1, findWays(steps, 1, 3)
|   |   |   |
|   |   |   |-- steps[3] = 1, findWays(steps, 0, 4) --> "1 1 1 1"
	        step[4]
	        step[3]
|   |   |
|   |   |-- steps[2] = 2, findWays(steps, 0, 3) --> "1 1 2"
|   |
|   |-- steps[1] = 2, findWays(steps, 1, 2)
|       |
|       |-- steps[2] = 1, findWays(steps, 0, 3) --> "1 2 1"
|
|-- steps[0] = 2, findWays(steps, 2, 1)
    |
    |-- steps[1] = 1, findWays(steps, 1, 2)
    |   |
    |   |-- steps[2] = 1, findWays(steps, 0, 3) --> "2 1 1"
    |
    |-- steps[1] = 2, findWays(steps, 0, 2) --> "2 2"


n=5

findWays(steps, 5, 0)
|
|-- steps[0] = 1, findWays(steps, 4, 1)
|   |
|   |-- steps[1] = 1, findWays(steps, 3, 2)
|   |   |
|   |   |-- steps[2] = 1, findWays(steps, 2, 3)
|   |   |   |
|   |   |   |-- steps[3] = 1, findWays(steps, 1, 4)
|   |   |   |   |
|   |   |   |   |-- steps[4] = 1, findWays(steps, 0, 5) --> "1 1 1 1 1"
|   |   |   |
|   |   |   |-- steps[3] = 2, findWays(steps, 0, 4) --> "1 1 1 2"
|   |   |
|   |   |-- steps[2] = 2, findWays(steps, 1, 3)
|   |       |
|   |       |-- steps[3] = 1, findWays(steps, 0, 4) --> "1 1 2 1"
|   |
|   |-- steps[1] = 2, findWays(steps, 2, 2)
|       |
|       |-- steps[2] = 1, findWays(steps, 1, 3)
|       |   |
|       |   |-- steps[3] = 1, findWays(steps, 0, 4) --> "1 2 1 1"
|       |
|       |-- steps[2] = 2, findWays(steps, 0, 3) --> "1 2 2"
|
|-- steps[0] = 2, findWays(steps, 3, 1)
    |
    |-- steps[1] = 1, findWays(steps, 2, 2)
    |   |
    |   |-- steps[2] = 1, findWays(steps, 1, 3)
    |   |   |
    |   |   |-- steps[3] = 1, findWays(steps, 0, 4) --> "2 1 1 1"
    |   |
    |   |-- steps[2] = 2, findWays(steps, 0, 3) --> "2 1 2"
    |
    |-- steps[1] = 2, findWays(steps, 1, 2)
        |
        |-- steps[2] = 1, findWays(steps, 0, 3) --> "2 2 1"




    
    
    
    
    */