ways-to-express-an-integer-as-sum-of-powers

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given two positive integers <code>n</code> and <code>x</code>.

Return the number of ways <code>n</code> can be expressed as the sum of the <code>xth</code> power of unique positive integers, in other words, the number of sets of unique integers <code>[n1, n2, ..., nk]</code> where <code>n = n1x + n2x + ... + nkx</code>.

Since the result can be very large, return it modulo <code>109 + 7</code>.

For example, if <code>n = 160</code> and <code>x = 3</code>, one way to express <code>n</code> is <code>n = 23 + 33 + 53</code>.

&nbsp;
Example 1:

<pre>
Input: n = 10, x = 2
Output: 1
Explanation: We can express n as the following: n = 32 + 12 = 10.
It can be shown that it is the only way to express 10 as the sum of the 2nd power of unique integers.
</pre>

Example 2:

<pre>
Input: n = 4, x = 1
Output: 2
Explanation: We can express n in the following ways:
- n = 41 = 4.
- n = 31 + 11 = 4.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 300</code></li>
	<li><code>1 &lt;= x &lt;= 5</code></li>
</ul>

numberOfWays

Ways to Express an Integer as Sum of Powers

Perfect Squares

perfect-squares

完全平方数

Combination Sum IV

combination-sum-iv

组合总和 Ⅳ

Target Sum

target-sum

目标和

Dynamic Programming

给你两个 正&nbsp;整数&nbsp;<code>n</code> 和&nbsp;<code>x</code>&nbsp;。

请你返回将&nbsp;<code>n</code>&nbsp;表示成一些&nbsp;互不相同&nbsp;正整数的&nbsp;<code>x</code>&nbsp;次幂之和的方案数。换句话说，你需要返回互不相同整数&nbsp;<code>[n1, n2, ..., nk]</code>&nbsp;的集合数目，满足&nbsp;<code>n = n1x + n2x + ... + nkx</code>&nbsp;。

由于答案可能非常大，请你将它对&nbsp;<code>109 + 7</code>&nbsp;取余后返回。

比方说，<code>n = 160</code> 且&nbsp;<code>x = 3</code>&nbsp;，一个表示&nbsp;<code>n</code>&nbsp;的方法是&nbsp;<code>n = 23 + 33 + 53</code>&nbsp;。

&nbsp;

示例 1：

<pre>输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 32 + 12 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。
</pre>

示例 2：

<pre>输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 41 = 4 。
- n = 31 + 11 = 4 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 300</code></li>
	<li><code>1 &lt;= x &lt;= 5</code></li>
</ul>