Permutations, Letter Combinations, Generate Parentheses.
Генерация всех перестановок и упорядоченных комбинаций. Используем backtracking с отслеживанием использованных элементов.
Условие:
Дан массив целых чисел nums с уникальными элементами. Верните все возможные перестановки в любом порядке.
Примеры:
Ввод: nums = [1,2,3]
Вывод: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Ввод: nums = [0,1]
Вывод: [[0,1],[1,0]]
Ввод: nums = [1]
Вывод: [[1]]
Ограничения:
💡 Подсказка: Проверяйте
if num not in path, чтобы не использовать элемент дважды.
nums = [1, 2, 3]
Дерево перестановок:
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2][1,3][2,1][2,3][3,1][3,2]
| | | | | |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
Порядок обхода:
1. [] → [1] → [1,2] → [1,2,3] ← добавляем
2. backtrack → [1,3] → [1,3,2] ← добавляем
3. backtrack → [] → [2] → [2,1] → [2,1,3] ← добавляем
4. backtrack → [2,3] → [2,3,1] ← добавляем
5. backtrack → [] → [3] → [3,1] → [3,1,2] ← добавляем
6. backtrack → [3,2] → [3,2,1] ← добавляем
Результат: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Решение:
def permute(nums):
result = []
def backtrack(path):
if len(path) == len(nums):
result.append(path[:])
return
for num in nums:
if num not in path: # Элемент ещё не использован
path.append(num)
backtrack(path)
path.pop()
backtrack([])
return resultОбъяснение:
if num not in path для отслеживания использованных элементовСложность:
Условие:
Дан массив целых чисел nums, который может содержать дубликаты. Верните все возможные перестановки в любом порядке.
Примеры:
Ввод: nums = [1,1,2]
Вывод: [[1,1,2], [1,2,1], [2,1,1]]
Ввод: nums = [1,2,3]
Вывод: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Ограничения:
💡 Подсказка: Используйте boolean массив used для отслеживания. Пропускайте дубликаты: if i > 0 and nums[i] == nums[i-1] and not used[i-1].
Решение:
def permuteUnique(nums):
nums.sort()
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
# Пропускаем дубликаты: если предыдущий такой же элемент не использован
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return resultОбъяснение:
used[i] отслеживает, используется ли элемент в текущем путиi > 0 and nums[i] == nums[i-1] and not used[i-1] — пропускаем дубликатыnot used[i-1] важно: пропускаем только если предыдущий дубликат не в текущем путиСложность:
Условие:
Дана строка digits, содержащая цифры от 2 до 9. Верните все возможные комбинации букв, которые могут быть представлены этими цифрами на телефонной клавиатуре.
Примеры:
Ввод: digits = "23"
Вывод: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Ввод: digits = ""
Вывод: []
Ввод: digits = "2"
Вывод: ["a","b","c"]
Ограничения:
💡 Подсказка: Используйте словарь для маппинга цифр в буквы. Отдельно обработайте пустую строку.
Решение:
def letterCombinations(digits):
if not digits:
return []
phone = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
result = []
def backtrack(index, path):
if index == len(digits):
result.append(path)
return
for letter in phone[digits[index]]:
backtrack(index + 1, path + letter)
backtrack(0, '')
return resultОбъяснение:
Сложность:
Условие:
Дано число n. Сгенерируйте все комбинации корректных скобочных последовательностей из n пар скобок.
Примеры:
Ввод: n = 3
Вывод: ["((()))","(()())","(())()","()(())","()()()"]
Ввод: n = 1
Вывод: ["()"]
Ограничения:
💡 Подсказка: Два условия: '(' можно добавить, если open_count < n; ')' можно добавить, если close_count < open_count.
Решение:
def generateParenthesis(n):
result = []
def backtrack(path, open_count, close_count):
if len(path) == 2 * n:
result.append(path)
return
# Можно добавить открывающую скобку
if open_count < n:
backtrack(path + '(', open_count + 1, close_count)
# Можно добавить закрывающую скобку
if close_count < open_count:
backtrack(path + ')', open_count, close_count + 1)
backtrack('', 0, 0)
return resultОбъяснение:
Сложность:
Условие:
Дана строка s. Разбейте s на подстроки так, чтобы каждая подстрока была палиндромом. Верните все возможные разбиения.
Примеры:
Ввод: s = "aab"
Вывод: [["a","a","b"],["aa","b"]]
Ввод: s = "a"
Вывод: [["a"]]
Ограничения:
💡 Подсказка: Проверяйте
is_palindrome(substring)перед добавлением в путь.
Решение:
def partition(s):
result = []
def is_palindrome(sub):
return sub == sub[::-1]
def backtrack(start, path):
if start == len(s):
result.append(path[:])
return
for i in range(start, len(s)):
substring = s[start:i+1]
if is_palindrome(substring):
path.append(substring)
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return resultОбъяснение:
Сложность:
Условие:
Дана строка s, содержащая только цифры. Верните все возможные валидные IP-адреса, которые можно получить из строки.
Валидный IP-адрес состоит из 4 чисел от 0 до 255, разделённых точками.
Примеры:
Ввод: s = "25525511135"
Вывод: ["255.255.11.135","255.255.111.35"]
Ввод: s = "0000"
Вывод: ["0.0.0.0"]
Ввод: s = "101023"
Вывод: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
Ограничения:
💡 Подсказка: Валидный сегмент: длина 1 ИЛИ (не начинается с '0' и значение ≤ 255).
Решение:
def restoreIpAddresses(s):
if len(s) < 4 or len(s) > 12:
return []
result = []
def is_valid(segment):
# '0' допустим, но '01', '001' — нет
return (len(segment) == 1 or
(segment[0] != '0' and int(segment) <= 255))
def backtrack(start, path):
if len(path) == 4:
if start == len(s):
result.append('.'.join(path))
return
for length in range(1, 4):
if start + length > len(s):
break
segment = s[start:start+length]
if is_valid(segment):
path.append(segment)
backtrack(start + length, path)
path.pop()
backtrack(0, [])
return resultОбъяснение:
Сложность:
| Задача | Ключевая идея |
|---|---|
| Permutations | if num not in path |
| Permutations II | used array + skip duplicates |
| Letter Combinations | phone dictionary mapping |
| Generate Parentheses | open < n, close < open |
| Palindrome Partitioning | is_palindrome check |
| Restore IP | is_valid segment (0-255) |
Проблема: Используем элемент дважды в перестановках.
# ❌ Неправильно — нет проверки
for num in nums:
path.append(num)
backtrack(path)
path.pop()
# ✅ Правильно — проверяем использованные
for num in nums:
if num not in path: # Элемент ещё не использован
path.append(num)
backtrack(path)
path.pop()Почему это неправильно: Один и тот элемент будет использоваться многократно.
Как исправить: Проверяйте if num not in path или используйте boolean массив used.
Проблема: Генерируем одинаковые перестановки.
# ❌ Неправильно — нет проверки дубликатов
nums = [1, 1, 2]
# Результат: [[1,1,2], [1,1,2], [1,2,1], [1,2,1], [2,1,1], [2,1,1]]
# ✅ Правильно — сортировка + проверка
nums.sort()
for i in range(len(nums)):
if used[i]:
continue
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue # Пропускаем дубликат
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = FalseПочему это неправильно: Одинаковые элементы генерируют одинаковые перестановки.
Как исправить: Сортировка + проверка i > 0 and nums[i] == nums[i-1] and not used[i-1].
Backtracking: Permutations — генерация всех упорядоченных комбинаций.
Ключевые принципы:
if num not in path или used array для отслеживанияi > 0 and nums[i] == nums[i-1] and not used[i-1]len(path) == len(nums) для перестановокВопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.