Perfect Squares

1. Problem Description

Given a positive integer n, find several perfect-square numbers (such as 1, 4, 9, 16, …) whose sum equals n. You need to minimize the number of perfect squares used.

Given an integer n, return the minimum number of perfect squares whose sum equals n.

A perfect square is an integer equal to the square of another integer; in other words, it is the product of an integer multiplied by itself. For example, 1, 4, 9, and 16 are perfect squares, while 3 and 11 are not.

2. Approach

• DFS: pruning + pass state as parameters
• DFS + memoization: enumeration + cache + return result

3. Implementation

3.1. DFS with Pruning

package main

import (
	"math"
)


func numSquares(n int) int {
	nums := make([]int, 0)
	for i := 1; i <= n; i++ {
		current := i * i
		if current <= n {
			nums = append(nums, current)
		}
	}

	min := math.MaxInt32
	size := 0
	numSquaresDFS(nums, len(nums)-1, n, &size, &min)
	return min
}

func numSquaresDFS(nums []int, index int, target int, size *int, min *int) {
	if target == 0 {
		*min = Min(*min, *size)
		return
	}

	for i := index; i >= 0; i-- {
		current := target - nums[i]
		if current >= 0 && *size+1 < *min {
			*size++
			numSquaresDFS(nums, i, current, size, min)
			*size--
		}

	}
}


func Min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

3.2. DFS + Memoization

func numSquares(n int) int {
    squares := make([]int, 0)
    for i := 1; i <= n; i++ {
        s := i * i
        if s > n {
            break
        }
        squares = append(squares, s)
    }

    memo := make(map[int]int, 0)
    count := numSquaresDFS(squares, n, memo)
    if count == math.MaxInt32 {
        return -1
    }
    return count
}

func numSquaresDFS(squares []int, target int, memo map[int]int) int {
    count, ok := memo[target]
    if ok {
        return count
    }

    if target < 0 {
        return math.MaxInt32
    }

    if target == 0 {
        return 0
    }

    count = math.MaxInt32
    for i:= 0; i < len(squares); i++ {
        count = min(count, numSquaresDFS(squares, target-squares[i], memo))
    }
    memo[target] = 1 + count
    return 1 + count

}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

4. References

• 279. Perfect Squares - LeetCode