Solving the LeetCode "Subsets" Problem in Go

Difficulty: Medium | Tags: Array, Backtracking, Bit Manipulation

Introduction

The "Subsets" problem requires generating all possible subsets of a given array of unique integers. This is a fundamental problem in combinatorics and backtracking, often used to test a developer's understanding of recursion and bit manipulation.

Problem Analysis

Given an array of unique integers, we need to return all possible subsets, including the empty set. For example, for the input [1, 2, 3], the output should include all combinations from the empty set to the full set: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].

Solution Approach

We can solve this problem using backtracking. The idea is to explore all possible combinations by recursively building subsets. For each element, we have two choices: include it in the current subset or exclude it. This approach ensures we cover all possible subsets without duplicates.

Go Implementation

func subsets(nums []int) [][]int {
    var result [][]int
    backtrack(nums, 0, []int{}, &result)
    return result
}
func backtrack(nums []int, start int, current []int, result *[][]int) {
    // Add the current subset to the result
    subset := make([]int, len(current))
    copy(subset, current)
    *result = append(*result, subset)
    // Explore further elements to add to the current subset
    for i := start; i < len(nums); i++ {
        current = append(current, nums[i])
        backtrack(nums, i+1, current, result)
        current = current[:len(current)-1] // Backtrack
    }
}

Complexity Analysis

Time Complexity: O(2^N), where N is the number of elements in the input array. This is because there are 2^N possible subsets.
Space Complexity: O(N) for the recursion stack, as the maximum depth of recursion is N.

Testing and Examples

Test Case 1:
Input: [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Test Case 2:
Input: [0]
Output: [[], [0]]

Best Practices and Tips

1. Use backtracking to explore all combinations efficiently.
2. Avoid modifying the original array to prevent unintended side effects.
3. Copy the current subset before adding it to the result to avoid reference issues.
4. For larger inputs, consider iterative approaches or bit manipulation for optimization.