Бэктрекинг

Бэктрекинг (поиск с возвратом) строит решение по шагам и откатывается назад, как только понимает, что текущая ветвь не приведёт к ответу. Это перебор, но с ранним отсечением (pruning), что резко сокращает число вариантов.

Сложность: в худшем случае экспоненциальная, но отсечения сильно её снижают на практике. Память: O(глубина рекурсии). Примеры: расстановка ферзей, судоку, генерация перестановок и подмножеств.

def permutations(a):
    res = []
    def backtrack(path, rest):
        if not rest:
            res.append(path[:])
            return
        for i in range(len(rest)):
            path.append(rest[i])
            backtrack(path, rest[:i] + rest[i + 1:])
            path.pop()        # возврат
    backtrack([], a)
    return res

print(len(permutations([1, 2, 3])))  # 6