Leetcode BiWeekly contest 109 - Medium - Ways to Express an Integer as Sum of Powers

In this video we discuss the fourth problem of Leetcode BiWeekly contest 109

[Rajat_maurya]

thank you man was using map for memo causing TLE <3

[mihirsaini]

Thanks sir, gr8 explanation as always!

[patuitar]

For this question I instantly thought Number of ways 0/1 Knapsack

[SahilShile]

Shit, I must have to right recursive first, I directly jump to iterative and Messed up😵‍💫

[durgaprasadvelagapudi]

missed the mod on include and exclude update. got TLE for 248 1 TC
class Solution {
List<Integer> nums = new ArrayList<>();
int mod = 1_000_000_007;
public int numberOfWays(int n, int x) {

for (int i = 1; i <= n; i++) {
int num = (int)Math.pow(i, x);
if (num > n){
break;
}
nums.add(num);
}
int len = nums.size();
int[][] memo = new int[len][n+1];
for (int[] m : memo)
Arrays.fill(m, -1);
return solve(0, 0, n, memo);
}

private int solve(int pos, int currSum, int n, int[][] memo){
// end reached
if (pos == nums.size()){
return (currSum == n) ? 1 : 0;
}
//back track
if (currSum > n)
return 0;

//memo
if (memo[pos][currSum] != -1)
return memo[pos][currSum];

int exclude = solve(pos + 1, currSum, n, memo) % mod;

int include = solve(pos + 1, currSum + nums.get(pos), n, memo) % mod;

return memo[pos][currSum] = (exclude + include) % mod;
}
}