JAVA:实现PowerSum幂和式算法(附完整源码)

package com.thealgorithms.backtracking;

import java.util.Scanner;


public class PowerSum {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the number and the power");
        int N = sc.nextInt();
        int X = sc.nextInt();
        PowerSum ps = new PowerSum();
        int count = ps.powSum(N, X);
        //printing the answer.
        System.out.println("Number of combinations of different natural number's raised to " + X + " having sum " + N + " are : ");
        System.out.println(count);
        sc.close();
    }
    private int count = 0, 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);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51