bool helper(char* input);

bool checkAB(char input[])
{
    if(*input!='a')
        return false;
    return helper(input);
}

bool helper(char *input)
{
    if(input[0]==0)
        return true;

    bool rule_2 = input[0]=='a' && (input[1]==0 || (input[1]=='a') || (input[1]=='b' && input[2]=='b'));
    if(rule_2)
        return helper(input+1);

    bool rule_3 = (input[0]=='b' && input[1]=='b') && (input[2]==0 || input[2]=='a');
     if(rule_3)
        return helper(input+2);

    return false;
}

int staircase(int n)
{
    if(n<0)
        return 0; // no possible way to do this

    if(n==0)    // i.e we took a full step of length 1 or 2 or 3. Mark it as 'a' step.
        return 1;
    // taking no step is also a single operation. i.e don't move 0C0. This will not affect our ops in any way

    // we take a step of length 1 or 2 or 3, the remaining length's way's into 1 for each term
    // i.e
    // 1 f(n-1)
    // 2 f(n-2)
    // 3 f(n-3)
    // add them up = 1*f(n-1) + 1*f(n-2) + 1*f(n-3) = f(n-1) + f(n-2) + f(n-3)

    return staircase(n-1) + staircase(n-2) + staircase(n-3);
}

//  Resources
//  https://www.youtube.com/watch?v=5o-kdjv7FD0
//  https://www.dailycodingproblem.com/?ref=csdojo

int helper(int* A, int start, int end, int &x)
{
    if(start==end)
    {
        if(A[start]==x)
            return start;
        return -1;
    } // base case

    if( x== A[(start+end)/2])     // calculation
        return (start+end)/2;
    else if(x < A[(start+end)/2])
        return helper(A, start, (start+end)/2 - 1, x); // recursive 1
    return helper(A, 1+(start+end)/2, end, x);    // recursive
}

int binarySearch(int input[], int size, int element) {
    // Write your code here
    if(size==0)
        return -1;
    return helper(input, 0, size-1, element);
}

int subset(int input[], int n, int output[][20])
{
    if (n == 0)
    {
        output[0][0] = 0; // length updated
        return 1;
    }

    int num = subset(input + 1, n - 1, output);

    // doing it in one go
    for (int i = 0; i < num; i++)
    {
        output[i + num][0] = output[i][0] + 1; // length updated
        output[i + num][1] = input[0];         // value prepended
        for (int j = 0; j < output[i][0]; j++)
        {
            output[i + num][j + 2] = output[i][j + 1];
        }
    }
    return 2 * num;
}

void helper(int *input, int n, int *output, int onum);

void printSubsetsOfArray(int input[], int size)
{
    int *b = new int[20];
    if (size != 0)
        helper(input, size, 0, 0);
}

void helper(int *input, int n, int *output, int onum)
{
    if (n == 0)
    {
        for (int i = 0; i < onum; i++)
            cout << output[i] << " ";
        cout << endl;
        delete[] output;
        return;
    }

    int *contrib = new int[onum + 1];
    // int *op2 = new int[onum];

    for (int i = 0; i < onum; i++)
        contrib[i] = output[i];

    contrib[onum] = input[0];

    helper(input + 1, n - 1, output, onum);
    helper(input + 1, n - 1, contrib, onum + 1);

    delete[] contrib;
}

/***
You need to save all the subsets in the given 2D output array. And return the number of subsets(i.e. number of rows filled in output) from the given function.

In ith row of output array, 1st column contains length of the ith subset. And from 1st column actual subset follows.
For eg. Input : {1, 3, 4, 2} and K = 5, then output array should contain
	{{2, 1, 4},	// Length of this subset is 2
	{2, 3, 2}}	// Length of this subset is 2

Don’t print the subsets, just save them in output.
***/

int subsetSumToK(int input[], int n, int output[][50], int k) {
    // Write your code here

}

void printSubsetSumToK(int input[], int size, int k)
{
    // Write your code here
}

#include <string.h>
using namespace std;

int getCodes(string input, string output[10000]) {
    /*
    You are given the input text and output string array. Find all possible codes and store in the output string array. Don’t print the codes.
    Also, return the number of codes return to the output string. You do not need to print anything.
    */
}

#include <string.h>
using namespace std;

void printAllPossibleCodes(string input)
{
    /*
    Given the input as a string, print all its possible combinations. You do not need to return anything.
    */
}

#include <string>
using namespace std;

int returnPermutations(string input, string output[])
{
   	/* Don't write main() function.
	 * Don't read input, it is passed as function argument.
	 * Print output as specified in the question
	*/
}

#include <iostream>
#include <string>
using namespace std;

void helper(string output, string input);

void printPermutations(string input)
{
    if(input.size()==0)
        return;
    helper("", input);
}

void helper(string output, string input)
{
    if(input.size()==0)
    {
        cout << output << endl;
        return;
    }

    int num = input.size();
    // just the shift function
    for(int i = 0; i < num; i++)
        helper(output + input[i], input.substr(0, i) + input.substr(i+1));

}

// in the second half of the call, we just do our move to front "move"