The Power Sum

Find the number of ways that a given integer, X, can be expressed as sum of the Nth powers of unique, natural numbers.

Input format:
The first line contains an integer X
The second line contains an integer N

Constraints:
1 <= X <= 1000
2 <= N <= 10

Output format:
Output a single integer, the answer to the problem explained above.

Sample Input 0

10
2

Sample Output 0

1

Explanation 0

If X = 10 and N = 2, we need to find the number of ways that 10 can be represented as the sum of squares of unique numbers.
10 = 1^2 + 3^2
This is the only way in which 10 can be expressed as the sum of unique square.

Sample Input 1

100
2

Sample Output 1

3

Explanation 1

100 = 10^2 = 6^2 + 8^2 = 1^2 + 3^2 + 4^2 + 5^2 + 7^2

Sample Input 2

100
3

Sample Output 2

1

Explanation 2

100 can be expressed as the sum of the cubes of 1,2,3,4.
(1 + 8 + 27 + 64) = 100. There is no other way to express 100 as the sum of cubes.

Approach 1:
With X = 10, and N = 2, this approach will generate sequences like:
[1]
[1, 4]
[1, 4, 9]
[1, 9]
[4]
[4, 9]
[9]
[9, 4]
and you can easily spot out the problem of this approach is it produces duplicated sequences. Here is the code:
def powerSum1(X, N):
    max_base = int(math.sqrt(X))
    sequence = list()
    ways = set()
    base = 1
    _recursive_sum1(X, N, base, max_base, sequence, ways)
    return len(ways)
    
def _recursive_sum1(X, N, base, max_base, sequence, ways):
    if sum(sequence) == X:
        # if set(sequence) not in ways:
        ways.add(tuple(sorted(sequence)))
        return False
    elif sum(sequence) > X:
        return False
    else:
        for i in range(base, max_base+1):
            tmp_val = i**N
            if tmp_val not in sequence:
                sequence.append(tmp_val)
                print(sequence)
                if _recursive_sum1(X, N, base+1, max_base, sequence, ways):
                    return True
                sequence.pop()
        return False
 If you remove the comment from the if statement, indent 1 tab to the right for the line above, it will work perfectly, but only for all possible small-enough numbers. Because it generates on possible sequences, sequences that are subsequently increment.
Approach 2:
This recursion type generate non-repeated sequences that are subsequently increment.
1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 6]
[1, 2, 3, 4, 7]
[1, 2, 3, 4, 8]
[1, 2, 3, 5]
[1, 2, 3, 5, 6]
[1, 2, 3, 5, 7]
[1, 2, 3, 6]
[1, 2, 3, 6, 7]
[1, 2, 3, 7]
[1, 2, 3, 8]
[1, 2, 3, 9]
[1, 2, 4]
def powerSum(X, N):
    sequence = list()
    base = 1
    look_up = [0]*(101)
    for i in range(1, 101):
        look_up[i] = i**N
    cur_sum = 0
    ways = _recursive_sum(X, N, base, look_up, cur_sum, sequence)
    return ways

def _recursive_sum(X, N, base, look_up, cur_sum, seq):
    ways = 0
    tmp_val = look_up[base]
    
    while cur_sum + tmp_val < X:
        seq.append(base)
        print(seq)
        ways += _recursive_sum(X, N, base+1, look_up, cur_sum+tmp_val, seq)
        seq.pop()
        base += 1
        tmp_val = look_up[base]

    if cur_sum + tmp_val == X:
        ways += 1
        seq.append(base)
        seq.pop()
    return ways