0

I am trying to write a program to solve a problem which states as follows "Print all possible distinct perfect squares whose sum is equal to the square of given number". For example -

Input

11

Output

1 4 16 36 64

1 4 16 100

4 36 81

I tried basic recursive approach and my code passed for small input. When I try for bigger number like 116 it runs forever. My JAVA code

public class SumOfPerfectSquare {
    public static void main(String args[]){
        generateSum(11);
    }

    private static void generateSum(int num) {
        int arr[] = new int[num];
        for(int i=1; i<num; i++){
            arr[i] = i*i;
        }
        findSum(arr, num*num, 1, 0, "");
    }

    private static void findSum(int arr[], int desiredSqr, int pointer, int currentSum, String sumStr) {
        if(pointer == arr.length || currentSum >= desiredSqr){
            if(currentSum == desiredSqr){
                System.out.println(sumStr);
            }
            return;
        }
        for(int i=pointer; i<arr.length; i++){
            findSum(arr, desiredSqr, i+1, currentSum+arr[i], sumStr+arr[i]+" ");
        }
    }
}

Please let me know if there is a better way to solve this (less time complexity)

Anakar
  • 112
  • 11
  • 2
    What about `1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1`? – n. m. could be an AI Aug 18 '17 at 20:04
  • Nopes need distinct perfect squares. I have edited the question to make it clear – Anakar Aug 18 '17 at 20:18
  • 1
    OK do you know how many solutions are there for 116? – n. m. could be an AI Aug 18 '17 at 20:33
  • You need to make use of [memoization](https://en.wikipedia.org/wiki/Memoization). – Aadit M Shah Aug 18 '17 at 20:47
  • @AaditMShah How exactly does memoisation help here? Note all components of the sum must be distinct. – n. m. could be an AI Aug 18 '17 at 20:56
  • It does help. When the sum is large enough, subproblems will appear multiple times. Memoization saves the answers to these subproblems so that you don't have to compute them again. Without memoization the time complexity is exponential. With memoization the time complexity becomes polynomial. – Aadit M Shah Aug 18 '17 at 21:09
  • @n.m. See my [answer](https://stackoverflow.com/a/45765643/783743) for more details on memoization. – Aadit M Shah Aug 18 '17 at 22:20
  • Memoization doesn't make the algorithm polynomial time but it still speeds it up quite a lot. – Aadit M Shah Aug 18 '17 at 22:29
  • I don't think the question has an answer. As @n.m. observes, there's over 67 billion solutions, so it's impossible to print them out efficiently. – Paul Hankin Aug 19 '17 at 08:01

2 Answers2

1

This can be done in O(n*sqrt(n)) by converting it into a subset sum problem. How?

consider all perfect squares which are less than or equal to N. The number of such elements would be sqrt(N).

Now are problem is in how many ways can we select a subset of these elements such that the sum = N.

Here is a discussion about this problem and you can find similar questions here.

The complexity of the problem if solved by Dynamic Programming would be O(n*sqrt(n))

Printing all these combinations would have O(sqrt(n)*2^(sqrt(n))) complexity, since their are 2^(sqrt(n)) subsets possible. We will have to check if this subset has sum = N.

Now if we traverse all numbers from 1 to 2^(srtn(N)-1). this number can represent all subsets which would be the indexes of the set bits it this number. traversing this number would take O(sqrt(N)) time.

So overall complexity O(sqrt(N) * 2^(sqrt(N))).

marvel308
  • 10,288
  • 1
  • 21
  • 32
0

Memoization certainly helps reduce the time complexity of this problem:

const memoize = callback => {
    const memo = new Map;

    return function () {
        const length = arguments.length, last = length - 1;

        let map = memo;

        for (let i = 0; i < last; i++) {
            const argument = arguments[i];
            if (!map.has(argument)) map.set(argument, new Map);
            map = map.get(argument);
        }

        const argument = arguments[last];
        if (!map.has(argument)) map.set(argument, callback.apply(null, arguments));
        return map.get(argument);
    };
};

const generateSums = memoize((sum, xs, index) => {
    if (sum === 0) return [[]];

    const result = [], length = xs.length;

    for (let i = index; i < length; i++) {
        const x = xs[i], diff = sum - x;
        let j = i + 1; while (xs[j] > diff) j++;
        const xss = generateSums(diff, xs, j);
        for (const xs of xss) result.push([x].concat(xs));
    }

    return result;
});

const solve = n => {
    const xs = [];
    for (let x = n - 1; x > 0; x--) xs.push(x * x);
    return generateSums(n * n, xs, 0);
};

console.time("Generate sums for 50²");
console.log(solve(50).length);
console.timeEnd("Generate sums for 50²");

Without memoization it takes significantly longer (beware, it might crash your browser):

const generateSums = (sum, xs, index) => {
    if (sum === 0) return [[]];

    const result = [], length = xs.length;

    for (let i = index; i < length; i++) {
        const x = xs[i], diff = sum - x;
        let j = i + 1; while (xs[j] > diff) j++;
        const xss = generateSums(diff, xs, j);
        for (const xs of xss) result.push([x].concat(xs));
    }

    return result;
};

const solve = n => {
    const xs = [];
    for (let x = n - 1; x > 0; x--) xs.push(x * x);
    return generateSums(n * n, xs, 0);
};

console.time("Generate sums for 50²");
console.log(solve(50).length);
console.timeEnd("Generate sums for 50²");

It still takes too much time to solve for 116 squared but this is a start.

Aadit M Shah
  • 72,912
  • 30
  • 168
  • 299