Generate All Subsets

LeetCode 78 · View on LeetCode

Generate all subsets using include/exclude recursion. For each element, either add it to the current subset or skip it, then recurse on the remaining elements.

package main

import "fmt"

func subsets(nums []int) [][]int {
	result := [][]int{}
	current := []int{}

	var backtrack func(start int)
	backtrack = func(start int) {
		tmp := make([]int, len(current))
		copy(tmp, current)
		result = append(result, tmp)

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

	backtrack(0)
	return result
}

func main() {
	fmt.Println(subsets([]int{1, 2, 3}))
	// [[] [1] [1 2] [1 2 3] [1 3] [2] [2 3] [3]]
}