Back to Repositories

Testing Subset Sum Algorithm Implementations in hello-algo

This test suite implements and verifies various subset sum algorithms in Go, testing both naive and optimized approaches for finding subsets that sum to a target value. The tests cover different implementations including handling of duplicate numbers and performance optimizations.

Test Coverage Overview

The test suite provides comprehensive coverage of three subset sum implementations:

TestSubsetSumINaive: Tests the naive implementation with potential duplicates
TestSubsetSumI: Verifies the basic optimized implementation
TestSubsetSumII: Tests handling of duplicate numbers in input array

Each test case validates the algorithm’s ability to find subsets summing to a target value using different input scenarios.

Implementation Analysis

The testing approach utilizes Go’s native testing framework with a focus on functional verification. Each test function follows a consistent pattern of setup, execution, and output validation.

Uses standard Go testing package for unit tests
Implements custom printing utilities for array visualization
Incorporates string conversion for detailed output logging

Technical Details

Testing infrastructure includes:

Go testing package (testing)
Custom printing utilities from hello-algo/pkg
strconv package for number-string conversion
fmt package for formatted output

Configuration includes standard Go test setup with imported custom utilities for array handling.

Best Practices Demonstrated

The test suite demonstrates several testing best practices:

Consistent test function naming convention
Clear separation of different implementation tests
Comprehensive output formatting for debugging
Modular test structure with reusable test data
Clear documentation of test purposes and expected outcomes

krahets/hello-algo

codes/go/chapter_backtracking/subset_sum_test.go

            
// File: subset_sum_test.go
// Created Time: 2023-06-24
// Author: Reanon ([email protected])

package chapter_backtracking

import (
	"fmt"
	"strconv"
	"testing"

	. "github.com/krahets/hello-algo/pkg"
)

func TestSubsetSumINaive(t *testing.T) {
	nums := []int{3, 4, 5}
	target := 9
	res := subsetSumINaive(nums, target)

	fmt.Printf("target = " + strconv.Itoa(target) + ", 输入数组 nums = ")
	PrintSlice(nums)

	fmt.Println("所有和等于 " + strconv.Itoa(target) + " 的子集 res = ")
	for i := range res {
		PrintSlice(res[i])
	}
	fmt.Println("请注意，该方法输出的结果包含重复集合")
}

func TestSubsetSumI(t *testing.T) {
	nums := []int{3, 4, 5}
	target := 9
	res := subsetSumI(nums, target)

	fmt.Printf("target = " + strconv.Itoa(target) + ", 输入数组 nums = ")
	PrintSlice(nums)

	fmt.Println("所有和等于 " + strconv.Itoa(target) + " 的子集 res = ")
	for i := range res {
		PrintSlice(res[i])
	}
}

func TestSubsetSumII(t *testing.T) {
	nums := []int{4, 4, 5}
	target := 9
	res := subsetSumII(nums, target)

	fmt.Printf("target = " + strconv.Itoa(target) + ", 输入数组 nums = ")
	PrintSlice(nums)

	fmt.Println("所有和等于 " + strconv.Itoa(target) + " 的子集 res = ")
	for i := range res {
		PrintSlice(res[i])
	}
}