I was solving this question on hackerearth -
https://www.hackerearth.com/problem/algorithm/supernatural-squad-2/description/

I came through the recurrence relation
(doesn't works correctly

```
if(dp[N][K] != -1)
return dp[N][K];
if(K == 0)
return 0;
if(K > N)
return 0;
if(N == K)
return 1;
else
{
dp[N-K][K] = solve(N-K,K); // Kth number is selected,problem reduced to subproblem with new sum as N - K
dp[N][K - 1] = solve(N,K - 1); // Kth number isn't selected,we need to explore upto (K - 1) now
dp[N][K] = dp[N-K][K] + dp[N][K - 1];
return dp[N][K];
}
```

instead of(works fine)

```
if(dp[N][K] != -1)
return dp[N][K];
if(K == 0)
return 0;
if(K > N)
return 0;
if(N == K)
return 1;
else
{
dp[N-K][K] = solve(N-K,K);
dp[N][K + 1] = solve(N,K + 1);
dp[N][K] = dp[N-K][K] + dp[N][K + 1];
return dp[N][K];
}
```

Whats the difference between 2 approaches for solving the above problem?

asked
**23 Dec '15, 16:05**

3★sandeep9

478●2●8●27

accept rate:
4%