package cn.iocoder.yudao.framework.common.thealgorithms.backtracking;

///*
// * Problem Statement :
// * Find the number of ways that a given integer, N , can be expressed as the sum of the Xth powers
// * of unique, natural numbers. For example, if N=100 and X=3, we have to find all combinations of
// * unique cubes adding up to 100. The only solution is 1^3+2^3+3^3+4^3. Therefore output will be 1.
// */
//public class PowerSum {
//
//    private int count = 0;
//    private int sum = 0;
//
//    public int powSum(int n, int x) {
//        sum(n, x, 1);
//        return count;
//    }
//
//    // here i is the natural number which will be raised by X and added in sum.
//    public void sum(int n, int x, int i) {
//        // if sum is equal to N that is one of our answer and count is increased.
//        if (sum == n) {
//            count++;
//            return;
//        } // we will be adding next natural number raised to X only if on adding it in sum the
//          // result is less than N.
//        else if (sum + power(i, x) <= n) {
//            sum += power(i, x);
//            sum(n, x, i + 1);
//            // backtracking and removing the number added last since no possible combination is
//            // there with it.
//            sum -= power(i, x);
//        }
//        if (power(i, x) < n) {
//            // calling the sum function with next natural number after backtracking if when it is
//            // raised to X is still less than X.
//            sum(n, x, i + 1);
//        }
//    }
//
//    // creating a separate power function so that it can be used again and again when required.
//    private int power(int a, int b) {
//        return (int) Math.pow(a, b);
//    }
//}

/*
 * 问题描述：
 * 找出一个给定整数 N 可以被表示为唯一自然数的 X 次幂之和的方法数。
 * 例如，如果 N=100 且 X=3，我们需要找到所有唯一立方数相加等于 100 的组合。
 * 唯一的解决方案是 1^3+2^3+3^3+4^3。因此输出将为 1。
 */
public class PowerSum {

    private int count = 0; // 解决方案的数量
    private int sum = 0; // 当前的和

    // 计算 N 可以被表示为唯一自然数的 X 次幂之和的方法数
    public int powSum(int n, int x) {
        sum(n, x, 1);
        return count;
    }

    // 这里的 i 是将被提升 X 次幂并加入和中的自然数
    public void sum(int n, int x, int i) {
        // 如果和等于 N，那么这是我们的一个答案，并且计数增加
        if (sum == n) {
            count++;
            return;
        } // 我们将添加下一个自然数提升到 X 次幂，只有在加上它后和小于 N 的情况下
        else if (sum + power(i, x) <= n) {
            sum += power(i, x);
            sum(n, x, i + 1);
            // 回溯并移除最后添加的数字，因为没有可能的组合包含它
            sum -= power(i, x);
        }
        // 如果 i 的 X 次幂小于 N，则在回溯后调用 sum 函数，使用下一个自然数
        if (power(i, x) < n) {
            sum(n, x, i + 1);
        }
    }

    // 创建一个单独的 power 函数，以便在需要时反复使用
    private int power(int a, int b) {
        return (int) Math.pow(a, b);
    }
}
