smallestNumberOfPerfectSquares

main.dart

import 'dart:math' as math;

// dislay detailed logs
bool enableLog = false;

// display iteration count
int iterationCount = 0;

// cache object
Map<int, List<int>> cache = {};

void main() {
  for (int i = 0; i < 150; i++) {
    // reset iteration count. it will be counted in function every call
    iterationCount = 0;
    var result = smallestNumberOfPerfectSquares(i);
    print('Given N = $i, return ${result.length} (${result.map((x) {
      return x * x;
    }).join(" + ")}), iteration: $iterationCount');
  }
}

// find smallest number of perfect squares
List<int> smallestNumberOfPerfectSquares(int n) {
  //print('--checking: $n');
  if (n < 1) return [];
  if (n == 1) return [1];

  // if we already calculated, present from cache
  if (cache.containsKey(n)) {
    if(enableLog) print('--from cache: $n');
    return cache[n];
  }

  // number list
  List<int> numbers = [];
  
  // start iteration from at the bigest squre number
  int start = math.sqrt(n).floor();
  int end = math.sqrt(n / 2).floor();
  
  if(enableLog) print('--n: $n, start: $start, end: $end');

  for (int i = start; i >= end; i--) {
    iterationCount++;
    List<int> tempNumbers = [i]; // add first number

    // find the rest
    var result = smallestNumberOfPerfectSquares(n - i * i);
    if (result.length > 0) {
      tempNumbers.addAll(result);
    }
    
    if(enableLog) print('----tempNumbers: $tempNumbers');
    
    // if first iteration or has less numbers
    if (numbers.length == 0 || tempNumbers.length < numbers.length) {
      numbers = tempNumbers;
    }
  }
  
  // update cache
  cache[n] = numbers;
  
  return numbers;
}