Subsets

Medium

The problem

Given a list of different numbers, return every possible subset (including the empty one and the full list). The subsets can come in any order.

Example 1
Input: nums = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
There are 8 subsets, because each of the 3 numbers is either in or out.
Example 2
Input: nums = [0]
Output: [[], [0]]

Limits

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
All numbers are different
The order of subsets, and of numbers inside each subset, does not matter

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

For each number there are two choices. What does the decision tree look like?

The idea

DFS(i): record the current subset, then for each j ≥ i choose nums[j], recurse with j+1, un-choose. (Or include/exclude per element.)

Target: O(n · 2^n) time

Go function shape

func subsets(nums []int) [][]int

Reference solution

Tested with go test. Try it yourself first, then compare.

// Subsets: every subset of distinct numbers.
// Every node of the decision tree is an answer, so we record on entry.
func Subsets(nums []int) [][]int {
	res := [][]int{}
	path := []int{}
	var dfs func(start int)
	dfs = func(start int) {
		res = append(res, append([]int(nil), path...))
		for i := start; i < len(nums); i++ {
			path = append(path, nums[i])
			dfs(i + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(0)
	return res
}

Read the lesson: Backtracking