Short Problem Definition:
Find the number of ways that a given integer, X , can be expressed as the sum of the Nth powers of unique, natural numbers.
For example, if X = 13 and N = 2, we have to find all combinations of unique squares adding up to 13. The only solution is 2^2 + 3^2.
time complexity is O(N!)
space complexity is O(1)
This solution does not use DP or memoisation, but it does not time out. We know that it needs to explore all P! possible combinations where P is floor(sqrt(X, N)). Since maximum X is 1000, this should still compute in real time.
Keep in mind that all integers in the solution have to be unique. So for X = 3, the solution 1^2 + 1^2 + 1^2 is not acceptable.
Did I mention that I dislike both NP-Hard problems and recursion? No? So, now you know.
def powerSum(X, N, current = 1): pw = pow(current, N) if pw > X: return 0 elif pw == X: return 1 else: return powerSum(X, N, current+1) + powerSum(X-pw, N, current+1)
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.