I already found this one
Brute force is possible of course, but are there any other ways? Is there a way to find all multisets? Is there a way to find out how many combinations exist under a certain limit?
Perhaps this question is too mathy for SO, if that is the case I'll move it.
I created my own version in javascript by generating all possible combinations of a list of numbers, then checking for integer RMS. These are sets though, not multisets.
Edit: I used N for sum value and K for the number of squares.
Number of multi-sets grows fast, so N should have reasonable value. So this problem is equivalent to changing sum N by K coins with nominals 1,4,9,25...
(and the number of variants might be calculated using dynamic programming).
The simplest implementation is recursive - we just generate all possible addends. In my Delphi implementation I collect summands in string (instead of list) for simplicity.
Note that such implementation might generate the same sequences again and again - note {5,7}
end-sequence in my example. To improve performance (important for rather large values of N and K), it is worth to store generated sequences in table or map (with {N;K;Min}
key). In that case generation from large summands to smaller ones would be better, because small summands give a lot of repeating patterns.
procedure FSP(N, K, Minn: Integer; Reslt: string);
var
i: Integer;
begin
if (K = 0) then begin
if (N = 0) then
Memo1.Lines.Add(Reslt); //yield result
Exit;
end;
i := Minn;
while (i * i <= N) do begin
FSP(N - i * i, K - 1, i, Reslt + Format('%d ', [i]));
i := i + 1;
end;
end;
procedure FindSquarePartitions(N, K: integer);
begin
FSP(N, K, 1, '');
end;
FindSquarePartitions(101, 5);
1 1 1 7 7
1 1 3 3 9
1 1 5 5 7
1 2 4 4 8
1 5 5 5 5
2 2 2 5 8
2 3 4 6 6
2 4 4 4 7
3 3 3 5 7