16 · ПЕРЕБОР

Backtracking

Выбери, углубись, отмени выбор — так строится дерево всех допустимых решений.

2 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Шаблон

path = append(path, choice)
dfs(next)
path = path[:len(path)-1]

Последняя строка восстанавливает состояние для соседней ветви.

Копия ответа

answer = append(answer,
    append([]int(nil), path...))

Без копии все ответы могут ссылаться на один массив.

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Все подмножества

На каждом уровне выбираем следующий элемент.

O(n · 2ⁿ) time · O(n) stack

solution.go

func subsets(nums []int) [][]int {
    out, path := [][]int{}, []int{}
    var dfs func(int)
    dfs = func(start int) {
        out = append(out, 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 out
}

ПРИМЕР РЕШЕНИЯ

Сумма комбинаций

Повторно используем элемент, пока остаток не отрицательный.

Exponential time · O(target/min) stack

solution.go

func combinationSum(nums []int, target int) [][]int {
    out, path := [][]int{}, []int{}
    var dfs func(int, int)
    dfs = func(start, rest int) {
        if rest == 0 { out = append(out, append([]int(nil), path...)); return }
        for i := start; i < len(nums) && nums[i] <= rest; i++ {
            path = append(path, nums[i]); dfs(i, rest-nums[i]); path = path[:len(path)-1]
        }
    }
    sort.Ints(nums); dfs(0, target)
    return out
}

ПРИМЕР РЕШЕНИЯ

Перестановки

Used-массив не позволяет повторно взять элемент в текущий путь.

O(n · n!) time · O(n) stack

solution.go

func permute(nums []int) [][]int {
    out, path, used := [][]int{}, []int{}, make([]bool, len(nums))
    var dfs func()
    dfs = func() {
        if len(path) == len(nums) { out = append(out, append([]int(nil), path...)); return }
        for i, n := range nums { if !used[i] {
            used[i] = true; path = append(path, n); dfs()
            path = path[:len(path)-1]; used[i] = false
        }}
    }
    dfs(); return out
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Определи состояние и варианты выбора
Добавь pruning как можно раньше
Копируй изменяемый путь в ответ