为何我的LeetCode递增子序列Golang代码出现TLE（超时）？

Hey there! Let's break down why your Go implementation is hitting a time limit exceeded (TLE) on the [1,2,...,15] test case, even when using the same algorithm as your working C++ version. The root cause almost always boils down to language-specific overheads that add up quickly with this problem's exponential number of valid subsequences.

Key Differences Between Go and C++ That Cause TLE #

1. Excessive Memory Allocation & GC Pressure #

Go's slices are convenient, but if your implementation creates a new slice for every recursive step (e.g., passing append(temp, nums[i]) directly to the recursive call), you're generating thousands of temporary slice objects. Each append may trigger a memory copy if the slice's capacity is exhausted, and Go's garbage collector (GC) has to clean up all these short-lived objects.

In contrast, C++'s vector lets you modify the same container in-place during backtracking (using push_back and pop_back), which avoids most of these extra allocations and has no GC overhead.

2. Inefficient Duplicate Checking with Maps #

If you're using a map[int]bool to track used elements in each recursive layer, that's a big bottleneck. Go's maps have inherent overhead from their concurrent-safe design (even in single-threaded code) and hash table operations.

C++'s unordered_set is faster for this use case, but even better—since LeetCode's problem constraints state that elements are between -100 and 100, you can use a fixed-size array for O(1) lookups, which blows maps out of the water.

3. Recursion Overhead #

Go's function call overhead is higher than C++'s, especially with recursion. For the [1,2,...,15] case, you're making ~32k recursive calls, and each call's overhead adds up. C++ compilers can optimize recursive calls more aggressively (like inline small functions) that Go's compiler might not.

Fixes to Get Your Go Code Passing #

1. Reuse Slices During Backtracking #

Instead of creating a new slice for every step, modify a single slice in-place and backtrack by truncating it:

func backtrack(nums []int, start int, temp []int, result *[][]int) {
    if len(temp) >= 2 {
        // Copy temp to result (since we'll modify temp later)
        *result = append(*result, append([]int{}, temp...))
    }
    // Use a fixed-size array instead of map for duplicate checking
    var used [201]bool // Covers -100 to 100 (index = num + 100)
    for i := start; i < len(nums); i++ {
        num := nums[i]
        if used[num+100] {
            continue
        }
        if len(temp) == 0 || num >= temp[len(temp)-1] {
            used[num+100] = true
            temp = append(temp, num)
            backtrack(nums, i+1, temp, result)
            temp = temp[:len(temp)-1] // Backtrack by truncating the slice
        }
    }
}

2. Preallocate Result Capacity #

Initialize your result slice with enough capacity to hold all possible valid subsequences. For n=15, that's 2^15 - 15 - 1 = 32752 elements:

result := make([][]int, 0, 32752)

This avoids repeated reallocations and copies as the result grows.

3. Replace Maps with Fixed-Size Arrays #

As shown in the code above, using [201]bool instead of map[int]bool eliminates hash table overhead entirely. This is a massive win for speed in duplicate checking.

4. (Optional) Switch to Iterative Implementation #

If recursion is still a bottleneck, you can rewrite the algorithm iteratively using a stack to track state. This avoids function call overhead, though it's more code.

Why This Works #

These changes address the biggest overheads in your Go code: reducing memory allocations, speeding up duplicate checks, and minimizing GC work. Your C++ code was already implicitly doing most of these optimizations (in-place vector modifications, faster set operations), which is why it passed the test case.

内容的提问来源于stack exchange，提问作者Suzy Zhang