Go Coding with Asparagos: Mushroom Soup for everyone!

#algorithms #go #beginners #tutorial

Everyone deserves creamy mushroom soup!

Hi! I'm Asparagos - an asparagus who codes in Go. Here you’ll find everyday problems that a typical veggie might struggle with — and my Go solutions to them. Today we are solving the problem of Mushroom Soup 🍄.

Problem

Autumn is a great time for soup, so the Veggie Kingdom is gathering mushrooms for a creamy mushroom soup. But there’s one problem: lactose intolerance. What's the solution? Cook two pots: one with dairy cream and one with coconut cream.

The amount of soup should be the same in both pots, so we need to split the mushrooms evenly by weight. Each mushroom has its own weight, so we can’t just divide them by count.

How can we quickly check whether it’s possible to partition the mushrooms into two groups with equal total weight?

Input 🥔

mushrooms []int - weights of the mushrooms (each element is the weight of one mushroom).

Output 🧅

Return true if it’s possible to partition the mushrooms evenly by weight (into two groups with equal total weight), otherwise return false.

Examples 🧄:

Example 1

Input: mushrooms = [1,5,11,5]

Output: true

The first pot contains mushrooms with weights 1, 5, 5, and the second pot contains a single mushroom with weight 11.
Example 2

Input: mushrooms = [1, 3, 10]

Output: false

It’s impossible to split the mushrooms into two groups with equal total weight.

Solution 💡

First, we calculate the total weight of all mushrooms. If totalWeight is odd, it's impossible to partition mushrooms evenly. Otherwise, the target weight for one pot is totalWeight / 2 (call it potWeight).
We use dynamic programming to solve the problem. Let's create a boolean slice dpSumWeight, where dpSumWeight[i] is true if some subset of mushrooms sums to i. We need potWeight+1 elements, because the maximum sum we care about is potWeight and we also add one element for zero weight.
We iterate through all the mushrooms. For each mushroom we scan dpSumWeight backwards. If dpSumWeight[i] is true and i+mushroomWeight < len(dpSumWeight), then set dpSumWeight[i+mushroomWeight] = true, because the sum i+mushroomWeight is now reachable. We go backwards so we don’t reuse the same mushroom twice during the same iteration.
If at any point dpSumWeight[potWeight] becomes true, we return true. Otherwise, return false.

func canPartition(mushrooms []int) bool {
    totalWeight := 0
    for _, mushroomWeight := range mushrooms {
        totalWeight += mushroomWeight
    }
    if totalWeight%2 == 1 {
        return false
    }
    potWeight := totalWeight / 2

    dpSumWeight := make([]bool, potWeight+1)
    dpSumWeight[0] = true
    for _, mushroomWeight := range mushrooms {
        for i := len(dpSumWeight) - 1; i >= 0; i-- {
            if dpSumWeight[i] && i+mushroomWeight < len(dpSumWeight) {
                dpSumWeight[i+mushroomWeight] = true
            }
        }
        if dpSumWeight[potWeight] {
            return true
        }
    }
    return false
}