# N Digit Sum Even Odd

Recursion

Hard

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given an integer `N`, print all `N`-digit numbers with sum of digits at `Even index` equal to sum of digits at `Odd index`.

See original problem statement here

#### For Example:

``````Input : N = 2

Output : 11 22 33 44 55 66 77 88 99

Explanation :

All these elements have sum at their odd indexes and sum at their even indexes equal.

11
sum at odd indexes = element at 1st index = 1
sum at even indexes = element at 0th index = 1

Similarly, all other elements 22, 33, 44, 55, 66, 77, 88, and 99.``````

Can we use `Recursion` here ?

Yes, we need to find all combinations that satisfies the following condition with the help of best online classes for coding with `Recursion`.

#### SOLVING APPROACH:

1. The idea is to generate all `N` digit combinations of digits `(0-9)` and check for those combinations that have sum at even indexes equal to sum at odd indexes.

2. Initialize an empty `string` for a combination, integers `odd` and `even` for maintaining the sum of odd and even index values, an integer `flag` for determining whether the current index is even or odd (`0` for even / `1` for odd).

3. Now recursively keep adding digits`(0-9)` to the `string` till its length become `N`.

4. Simultaneously keep adding odd-indexed value to `odd` and even-indexed value to `even`.

5. When length of `string` becomes `N`, check if `even` is equal to `odd`. If `Yes` we get our valid combination.

NOTE: One important observation is, leading `0`'s must be
handled explicitly as they are not counted as digits.

#### ALGORITHM:

``````str = ""
flag = 0
even = 0
odd = 0

NdigitNumEO (str, n, even, odd, flag)
if (length of str is equal to n and even is equal to odd)
print str

Run loop from d = '0' to '9'
If (flag is 0)
NdigitNumEO (str+d, n-1, even + (d - '0'), odd, 1)

else
NdigitNumEO (str+d, n-1, even, odd + (d - '0'), 0)
``````

#### SOLUTIONS:

```
#include <stdio.h>
#include <string.h>

/* function for appending a char to a char array */
void append(char* s, char c) {
int len = strlen(s);
s[len] = c;
s[len+1] = '\0';
}

void solve(char *s, int n, int odd, int even, int flag){
if(n){
char d = '0';

char empty[] = "";
if(strcmp(s, empty) == 0) d = '1';

for(;d<= '9';d++){

/* creating a temporary char array */
char str;

/* copying original char array to temp array */
strcpy(str, s);

/* append char i to char array str */
append(str, d);

if(flag)
solve(str, n-1, odd+(d-'0'), even, 0);
else
solve(str, n-1, odd, even+(d-'0'), 1);
}
}
if(n == 0 && even == odd){
printf("%s ", s);
}
}
int main(){
int n; scanf("%d", &n);
char s = "";
int odd = 0;
int even = 0;
int flag = 0;
solve(s, n, odd, even, flag);
return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;

void solve(string s,int n,int odd,int even,int flag){
if(n){
char d = '0';
if(s == "") d = '1';

for(;d<= '9';d++){

if(flag)
solve(s+d,n-1,odd+(d-'0'),even,0);
else
solve(s+d,n-1,odd,even+(d-'0'),1);
}
}
if(n == 0 && even == odd){
cout<<s<<" ";
}
}
int main(){

int n; cin>>n;
string s = "";
int odd = 0;
int even = 0;
int flag = 0;

solve(s, n, odd, even, flag);

return 0;
}

```
```
import java.util.*;
import java.io.*;

public class Main {

/* Use StringBuffer class in case we have to print large number of data
this avoids chances of TLE */
static StringBuffer sb = new StringBuffer();

static void solve(String s,int n,int odd,int even,int flag){
if(n > 0){
char d = '0';
if(s == "") d = '1';

for(;d<= '9';d++){
if(flag == 1)
solve(s+d,n-1,odd+(d-'0'),even,0);
else
solve(s+d,n-1,odd,even+(d-'0'),1);
}
}

if(n == 0 && even == odd){
// Using string buffer to append each output in a string
sb.append(s + " ");
}
}
public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String s = "";
int odd = 0, even = 0, flag = 0;

solve(s, n, odd, even, flag);

System.out.print(sb);
}
}

```