## 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.

[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

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

## Reply