NUHMAN.com

Introduction

LeetCode 78: Subsets is a fundamental backtracking problem where you're asked to generate all possible subsets (the power set) of a given set of integers. This classic question is essential for mastering recursion, backtracking, and bit manipulation techniques.

Problem Statement

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets, and you may return the subsets in any order.

Example:

go

Input: nums = [1,2,3]
Output: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

Approach: Backtracking (Recursive DFS)

We’ll use a recursive backtracking approach:

• At each step, we choose whether to include the current element or exclude it.
• We explore all such combinations recursively.
• We maintain a temporary slice to build the current subset.

Go Implementation

go

func subsets(nums []int) [][]int {
    var res [][]int
    var path []int

    var dfs func(start int)
    dfs = func(start int) {
        // Make a copy of path and append it to result
        subset := make([]int, len(path))
        copy(subset, path)
        res = append(res, subset)

        for i := start; i < len(nums); i++ {
            path = append(path, nums[i])       // choose
            dfs(i + 1)                          // explore
            path = path[:len(path)-1]           // un-choose (backtrack)
        }
    }

    dfs(0)
    return res
}

Explanation

• dfs is a recursive function that explores all combinations starting from index start.
• At each level, we either include the element or skip to the next.
• We store a copy of the current path in the result each time we reach a new node in the recursion tree.
• We backtrack by removing the last added element after the recursive call.

Time and Space Complexity

MetricComplexityTime ComplexityO(2ⁿ)Space ComplexityO(2ⁿ)

Where n is the number of elements in the input list. Each element has two choices: include or exclude.

Alternative Approach: Bitmasking

Each subset can be represented by a binary number of length n. Iterate from 0 to 2ⁿ - 1, using bits to decide inclusion.

Edge Cases

• Empty array → returns [[]]
• Array with 1 element → returns [[], [num]]
• Unordered output is acceptable

Conclusion

LeetCode 78 is a classic recursion problem that sharpens your backtracking and subset-generation skills. Whether you use backtracking or bitmasking, it’s a must-know for technical interviews.

Solving this in Go improves your understanding of slices, recursive closures, and copy mechanics—valuable tools for idiomatic Go coding.