Start learning free

LESSON 355 OF 540 · BACKTRACKING

Subsets in Go: Backtracking, O(n · 2^n)

Practice O(n · 2n) Read the full explanation

Given an array nums of distinct integers, return every subset of nums: every way to pick some of its numbers, from none of them (the empty subset) to all of them.

Write the numbers of each subset in the order they have in nums. Return the subsets in the order you get by deciding about the numbers one at a time, skipping before taking: every subset without nums[0] comes before every subset with it; inside each of those two groups, the subsets without nums[1] come before the ones with it, then the same for nums[2], and so on. So the empty subset always comes first, and all of nums comes last.

 

Example 1:

Input: nums = [1,2,3]
Output: [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
Explanation: The first four subsets skip 1, the last four take it.
Among the first four, [] and [3] skip 2, while [2] and [2,3] take it; in each pair, the one without 3 comes first.
The last four are the same four with 1 in front.

Example 2:

Input: nums = [0]
Output: [[],[0]]
Explanation: With one number there are two subsets: without it, then with it.

Example 3:

Input: nums = [3,-1]
Output: [[],[-1],[3],[3,-1]]
Explanation: The subsets without 3 come first. The last subset is written [3,-1], in the order of nums, not sorted.

 

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers in nums are distinct.

Note:

The tutorial uses backtracking. Walk through nums one index at a time, keeping the numbers taken so far in a list current. At index i, first skip nums[i]: go on to index i + 1 with current as it is. Then take it: add it to current, go on to index i + 1, and remove it again. When the index reaches the end of nums, every number has been skipped or taken: save a copy of current. Trying skip before take gives exactly the order above. It is the same choice as when you generate binary strings: a subset is a string of n bits, 0 for skip and 1 for take, and the subsets come out in the order of those strings.

There are 2n subsets and copying one takes up to n steps, so the time is O(n · 2n). Besides the answer, the extra space is O(n): the subset being built and one call per index.

STEP 1 OF 10
    Ctrl + Enter to check

    GO · BACKTRACKING

    Subsets in Go, explained

    Problem overview

    The function subsets(nums []int) [][]int receives a slice of distinct integers and returns every subset: every way to pick some of the numbers, from none of them (the empty subset) up to all of them. Each subset keeps the order its numbers have in nums.

    The order of the answer is fixed too. The search decides about the numbers one at a time, skipping before taking. Every subset without nums[0] comes before every subset with it. Inside each of those two groups, the subsets without nums[1] come first, and so on. The empty subset is always first and all of nums is last.

    For nums = [1, 2, 3] the answer is [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]. The first four subsets skip 1 and the last four take it. For [3, -1] the answer is [[], [-1], [3], [3, -1]]: the last subset is written in the order of nums, not sorted.

    Approach: skip or take, one number at a time

    A subset is a series of yes/no decisions, one per number. With n numbers there are 2^n series, so there are 2^n subsets: 8 for three numbers, 1,024 for ten. The answer is that big whatever the method, so the goal is to generate each subset exactly once with little extra work.

    Backtracking does it with a recursive function that handles one index i at a time and keeps the numbers taken so far in a slice called current:

    • At index i, first skip nums[i]: recurse on i + 1 with current unchanged.
    • Then take it: add it to current, recurse on i + 1, and remove it again.
    • When i reaches len(nums), every number has been decided: current is a finished subset, and a copy of it goes in the result.

    Trying skip before take produces exactly the order the statement describes. It is the same order as counting in binary with 0 for skip and 1 for take: 000, 001, 010, and so on.

    Taking, recursing and then removing is the "back" in backtracking. Each call gives back what it took, so the caller finds current as it left it.

    Step by step

    1. Create result as an empty [][]int, written [][]int{}. Each element is a subset, so it holds slices.
    2. Start the search with backtrack(nums, 0, []int{}, &result). Nothing is decided yet, so the index is 0 and the subset so far is empty. The last argument is the address of result: append can return a new slice, and the helper has to store it where subsets can see it.
    3. Return result after the call.
    4. Declare the helper backtrack(nums []int, i int, current []int, result *[][]int). It returns nothing. The type *[][]int is a pointer to a slice of slices.
    5. Base case. If i == len(nums), every number has been skipped or taken.
    6. Save a copy. *result = append(*result, append([]int{}, current...)) appends a fresh copy of current to the slice the pointer points to, then return.
    7. Skip. Call backtrack(nums, i+1, current, result) without touching current. Doing this first puts all subsets without nums[i] before those with it.
    8. Take. Append nums[i] to current and store the result back in current.
    9. Recurse again with the same arguments. Now current holds nums[i], so this call finds every subset that contains it.
    10. Undo. Set current to current[:len(current)-1], the slice without its last element.

    The solution in Go

    func subsets(nums []int) [][]int {
	result := [][]int{}
	backtrack(nums, 0, []int{}, &result)
	return result
}

func backtrack(nums []int, i int, current []int, result *[][]int) {
	if i == len(nums) {
		*result = append(*result, append([]int{}, current...))
		return
	}
	backtrack(nums, i+1, current, result)
	current = append(current, nums[i])
	backtrack(nums, i+1, current, result)
	current = current[:len(current)-1]
}

    The Go details that matter here:

    • Why a pointer to result. Go passes slices by value: the callee gets a copy of the slice header (pointer, length, capacity). When append grows the slice, the new header exists only in the variable that received it. Passing *[][]int lets backtrack write the grown slice through *result, and subsets sees it.
    • Why copy current. Slices that come from append can share one backing array, and current keeps changing as the search goes on. append([]int{}, current...) builds a new slice with its own array, so a saved subset never changes later. Without the copy, the results for [1, 2, 3] happen to look right, but for [1, 2, 3, 4, 5] the output lists [1 2 3 4] twice and has no [1 2 3 5].
    • The current... spread. It passes the elements of a slice as separate arguments to the variadic append.
    • The last line is a habit more than a need. current is a parameter, so the caller's slice header keeps its old length whatever this call does. Trimming it is still the natural way to write "give back what you took", and it keeps the code correct if the structure changes.
    • Slice expressions. current[:len(current)-1] takes the elements from index 0 up to, but not including, the last one. It doesn't copy anything.

    Complexity

    Time: O(n · 2^n). The recursion has 2^n leaves, one per subset, and about 2^(n+1) calls in all. Each leaf copies a subset of up to n numbers, which costs up to n steps. For n = 10 that is 1,024 subsets.

    Space: O(n) besides the answer. The recursion is n + 1 calls deep, and current holds at most n numbers. The answer itself needs O(n · 2^n), but that is the output, not extra work.

    Edge cases and common mistakes

    • One number. [0] gives [[], [0]]: without it, then with it.
    • The empty subset is part of the answer. It is always first. Forgetting it, or starting the result with only the single-number subsets, loses it.
    • Saving current itself. Appending current without copying stores a slice that later calls can overwrite. It can pass on small inputs, which makes it a hard bug to see.
    • Taking before skipping. That gives the same subsets in a different order, and the lesson's tests expect skip-first.
    • Sorting each subset. The numbers of a subset stay in the order of nums: for [3, -1] the last subset is [3, -1], not [-1, 3]. Adding numbers in index order gives that for free.
    • Forgetting the pointer. If result were passed by value, the appended subsets would be lost when backtrack returns, and subsets would return an empty slice.
    • Wrong base case. Stopping at len(nums) - 1 misses the decision about the last number.

    Testing

    • [1, 2, 3] gives [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]].
    • [0] gives [[], [0]].
    • [3, -1] gives [[], [-1], [3], [3, -1]].
    • [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] gives 1,024 subsets.
    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free