The array-based backtracking is commonly used in problems involving subsets, combinations, and permutations.

1. Recursive Exploration: The elements in the array determine the choices. We try out different choices and backtrack when a choice does not lead to a solution.
2. Pruning (Optimization): We can cut off unnecessary branches using conditions to reduce redundant computations.

Think of it as DFS in a decision tree, without spending extra time and space (O(n^2)) converting it into an Adjacency List.

[] [1] [2] [3] [1,2] [1,3] [2,3] [1,2,3]

Typical result size: 2^n | Choose k elements out of n

[1,2] [1,3] [2,3]

(if k = 2)

Typical result size: C(n, k) (n choose k) | Choose n elements out of n (when elements are unique)

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

Typical result size: n! (factorial of n) | | Order matters? | ❌ No

[1, 2] and [2, 1] → same subset | ❌ No

[1, 2] and [2, 1] → same combination | ✅ Yes

[1, 2] and [2, 1] → different permutations | | Code structure | DFS structure: Include/exclude each element

When to push result: Push at every recursion level | DFS structure: Include/exclude each element (Two combinations picking from the same index [2(idx0), 3(idx1)] and [3(idx1), 2(idx0)] are considered the same combination, this approach allows us not picking the index from the back)

When to push result: Push when result length is k. | DFS structure: At each level, loop through all elements, and choose any not-yet-used element.

When to push result: Push when result length is n. | | Analogy | You’re invited to parties (n), you can decide to go or not. | You’re picking courses (n) in university to match the credit (k). | You’re arranging seats (n) at a dinner, the order matters. |

(Medium) 78. Subsets

https://leetcode.com/problems/subsets

Last review: Jun 13, 2025 Next review: No need to review

All elements are unique.

1. Start from an empty subset [] at the root.
2. Each element (step) has 2 decisions (include or exclude), the total number of subsets for n elements is 2^n.
3. In the design tree, it will have 2^n nodes with n height.

Left  -> Include current node and add
Right -> Exclude current node
The subset is pushed at leaf nodes.
                               []
                       /                \\
                   [1]                    []
                  /    \\                /    \\
            [1,2]        [1]         [2]       []
           /     \\      /   \\       /   \\     /   \\
     [1,2,3]   [1,2] [1,3]  [1]  [2,3]  [2] [3]    []

Another tree representation reflecting the code process:

Left  -> Include current node and add
Right -> Exclude current node and add
The subset is pushed at every nodes.
                 []
                /    
              [1]
           /       \\
       [1,2]        [2]
      /     \\       /  \\
[1,2,3]   [1,3] [2,3]  [3]

DFS (Side-Effect)

Recursion

• Time Complexity O(n * 2^n)
  • DFS takes O((2^n - 1) + 2^n) = O(2^n) time traversing all edges and nodes
  • At each node, pushing element (copy) to result takes O(1 ~ n) = O(n) time
• Space Complexity O(max(n, n * 2^n)) = O(n * 2^n)
  • DFS takes O(n) space stacking number of height of frames
  • In the result storage, each subset can take up to O(n) space, the number of subset is 2^n.

func subsets(nums []int) [][]int {
	res := make([][]int, 0, 1<<len(nums)) // 1 * 2^len
	res = append(res, []int{})

	// i: next index
	// comb: current sebset
	var dfs func(i int, comb []int)
	dfs = func(i int, comb []int) {
		if i >= len(nums) {
			return
		}

		comb = append(comb, nums[i])

		// copy `comb` cause the indexs' value in underlying array can be change by other combinations
		res = append(res, append([]int{}, comb...))

		// include the current one (in comb) and go next
		dfs(i+1, comb)
		// exclude the current one (in comb) and go next
		comb = comb[:len(comb)-1]
		dfs(i+1, comb)
	}

	dfs(0, []int{})
	return res
}

// Or

func subsets(nums []int) [][]int {
	res := make([][]int, 0, 1<<len(nums)) // 1 * 2^len

	// i: current index
	// comb: current sebset
	var dfs func(i int, comb []int)
	dfs = func(i int, comb []int) {

		// copy `comb` cause the indexs' value in underlying array can be change by other combinations
		res = append(res, append([]int{}, comb...))

		for j := i + 1; j < len(nums); j++ {
			dfs(j, append(comb, nums[j]))
		}
	}

	dfs(-1, []int{})
	return res
}