# TLE but correct Java recursive solution.

• ``````public class Solution {
public int numWays(int n, int k) {
if(k==0||n==0)return 0;
if(n<=2&&k==1){
return 1;
}
if(n==1&&k>=1){
return k;
}
return helper(n,k,1,false,k);
}
public int helper(int n,int k,int i, boolean last_two_same, int currproduct){
if(i<n-1){
if(last_two_same==true){
return helper(n,k,i+1,false,(k-1)*currproduct);
}
else{
return helper(n,k,i+1,true,currproduct) + helper(n,k,i+1,false,(k-1)*currproduct);
}
}
else{//i==n-1
if(last_two_same==true){
return (k-1)*currproduct;
}
else{
return k*currproduct;
}
}
}
}
``````

The main idea is similar to using 2d array to store the information. I use a helper function to record if the last 2 posts share the same color and the current product of one condition.

• yeah same here, can not pass the last case, so sad. I wonder in real interview do we have to write iterative solution rather than recursion?

``````public int numWays(int n, int k) {
if (n == 1) return k;
if (k == 0 || n == 0)  return 0;
//n!=1 or 0 now
if (k == 1) {
if (n == 2) return 1;
else return 0;
}

int res = k *(helper(true, 1, n - 1, k) + helper(false, 1, n - 1, k));
return res;
}
private int helper(boolean same, int i, int bound, int k) {
if (i == bound) {
if (same) return 1;
else return k - 1; // x = k - 1
}
else {
if (same) return helper(false, i + 1, bound, k);
else return (k - 1) * (helper(true, i + 1, bound, k) + helper(false, i + 1, bound, k));
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.