I have an algorithmic question: How can we determine if a number equals the sum of some different squared numbers? For example : 50 = 4*4 5*5 3*3

I am ok with 2 numbers and I know that We can solve it with Recursion.

Here is my code in java for 2 numbers :

import java.util.Scanner;

public class SemiCharismatic {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int number = input.nextInt();
        input.close();
        if (isSquare(number) == true) {
            System.out.print("YES");
            System.exit(0);
        } else {
            for (int i = 1; i < number; i  ) {
                int j = number - i;
                if (isSquare(i) == true && isSquare(j) == true) {
                    System.out.print("YES");
                    System.exit(0);
                }
            }
            System.out.print("NO");
        }
    }

    static boolean isSquare(int number) {
        boolean result = false;
        if (Math.sqrt(number) - Math.floor(Math.sqrt(number)) == 0) {
            result = true;
        }
        return result;
    }
}

CodePudding user response：

This problem is a variant of Subset sum problem.

Here you'll have to create a set of your own (which is explained below) and your number is the target sum for the problem.

To create a set, form an array of numbers [square of numbers from {1 to sqrt(n)}]

So your array will look like: [1,4,9... sqrt(n)^2]

To explain why sqrt(n): The square of any number greater than sqrt(n) will also be greater than n. Hence adding more to it will not lead to a solution.

Then apply the subset-set algorithm, as explained here

isSubsetSum(set, n, sum) 
= isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0 

CodePudding user response：

I would try and solve this as a graph search problem.

Defining the states

In this problem I will define the states as a tuple of (current_number, set_of_candidates). This means that the initial state will we the input number and the candidate set will we all the squared integers lower than the input number For convenience, we will keep track of the used candidates in each state. For example when the input is 50, the starting state will be:

state = [50, {1, 4, 9 ,16,25, 36, 49}, []]

See that state[0] is the input number, state[1] is a set of all the squared integers where the squared value is lower than the target and state[2] is empty since we did not use any candidates.

Defining the transitions

The transitions between states will be to deduct from state[0] a number from the set, as well as removing the same number from the set. This means that we will not return to any state twice and thus we will not keep track of a visited states.

Solution proposal

After defining the states and transitions, any graph search algorithm will solve your problem. In case you want to find the minimal number of candidates to make up the target number, we will use BFS (read more on BFS and DFS here). A python implementation of this will be:

import collections
import numpy as np

def is_sum_squared(number):
    # Starting Variables
    state_queue = collections.deque([]) # Pending states which have not been explored yet
    # Computing the starting set, all squared numbers from 1^2 to floor(sqrt(number))^2
    candidates  = np.arange(1, int(np.ceil(np.sqrt(number)))) ** 2
    state       = [number, set(candidates), []]  # Starting state
    while state[0] > 0:
        # Getting all possible neighboring states and adding to the stack / queue. NOTE we are not visiting a state twice, therefore we do not keep a visited set
        for candidate in state[1]:
            if state[0] - candidate >= 0:
                temp_set = state[1].copy()
                temp_set.remove(candidate)
                state_queue.append([state[0] - candidate, temp_set, state[2]   [candidate]]) if temp_set is not None else None
        # popping next state from the queue and updating the path if needed
        try:
            state = state_queue.popleft()
        except IndexError:
            return -1
    return np.sqrt(state[2])

Note that the difference between BFS and DFS is that the BFS uses a queue whereas the DFS uses a stack, therefore we can change this to DFS via changing state = state_queue.popleft() to state = state_queue.pop(). Using this function with the input of 50 returns [1, 7] which means

1**2   7**2 = 1   49 = 50