Определение

Перебор с возвратом - основан на пошаговом переборе всех возможных вариантов решения, при этом осуществляется отслеживание состояния и возврат к предыдущему шагу, если текущий вариант не приводит к решению.

Примеры задач

Задача №1

Дано множество чисел и целевое значение суммы. Определите, существует ли комбинация чисел, которая в сумме дает целевое значение.

Решение

1. Для каждой комбинации чисел рекурсивно проверять, дает ли их сумма целевое значение.

2. Если текущая сумма равна целевому значению, возвращаем true.

3. Если текущая сумма превышает целевое значение или мы перебрали все числа, возвращаем false.

Псевдокод

Функция рекурсия(индекс, текущая_сумма, числа, целевая_сумма):  
    если текущая_сумма == целевая_сумма:  
        вернуть Правда  
    если текущая_сумма > целевая_сумма или индекс == длина(числа):  
        вернуть Ложь  
  
    если рекурсия(индекс + 1, текущая_сумма + числа[индекс], числа, целевая_сумма):  
        вернуть Правда  
    если рекурсия(индекс + 1, текущая_сумма, числа, целевая_сумма):  
        вернуть Правда  
  
    вернуть Ложь  
  
Функция решить(числа, целевая_сумма):  
    вернуть рекурсия(0, 0, числа, целевая_сумма)

Реализация на Python

Аннотация:  
backtrack - рекурсивная функция, реализующая метод перебора с возвратом для поиска комбинации чисел  
numbers - список целых чисел  
target_sum - целевая сумма  
current_sum - текущая сумма выбранных чисел  
solve - функция для определения, существует ли комбинация чисел из списка, сумма которых равна заданному значению

def backtrack(numbers, target_sum, index, current_sum):  
    if current_sum == target_sum:  
        return True  
    if current_sum > target_sum or index == len(numbers):  
        return False  
  
    if backtrack(numbers, target_sum, index + 1, current_sum + numbers[index]):  
        return True  
    if backtrack(numbers, target_sum, index + 1, current_sum):  
        return True  
  
    return False  
  
def solve(numbers, target_sum):  
    return backtrack(numbers, target_sum, 0, 0)

Олимпиадная реализация на C++

Аннотация:  
typedef - переопределение имени типа данных  
dfs - рекурсивная функция для определения, существует ли комбинация чисел, сумма которых равна заданному значению, используя глубину поиска  
nums - список целых чисел  
target - целевая сумма  
sum - текущая сумма выбранных чисел  
solve - функция для определения, существует ли комбинация чисел, сумма которых равна заданному значению

typedef vector<int> vi;  
  
bool dfs(const vi nums, int target, int idx, int sum) {  
  if (sum == target) return true;  
  if (sum > target || idx == nums.size()) return false;  
  
  return dfs(nums, target, idx + 1, sum + nums[idx]) ||  
         dfs(nums, target, idx + 1, sum);  
}  
  
bool solve(const vi nums, int target) return dfs(nums, target, 0, 0);

Продуктовая реализация на C++

Аннотация:  
backtrack - рекурсивная функция, реализующая метод перебора с возвратом для поиска комбинации чисел  
numbers - список целых чисел  
target_sum - целевая сумма  
current_sum - текущая сумма выбранных чисел   
solve - функция для определения, существует ли комбинация чисел из списка, сумма которых равна заданному значению

bool backtrack(const vector<int>& numbers, int target_sum, int index,  
               int current_sum) {  
  if (current_sum == target_sum)  
    return true;  
  if (current_sum > target_sum || index == numbers.size())   
    return false;  
  
  if (backtrack(numbers, target_sum, index + 1, current_sum + numbers[index]))  
    return true;  
  if (backtrack(numbers, target_sum, index + 1, current_sum))  
    return true;  
  
  return false;  
}  
  
bool solve(const vector<int>& numbers, int target_sum) {  
  return backtrack(numbers, target_sum, 0, 0);  
}

Задача №2

Дана строка. Найдите все возможные перестановки символов в строке.

Решение

1. Рекурсивно генерировать перестановки, меняя символы местами.

2. Если текущая позиция равна длине строки, добавить текущую перестановку к результату.

Псевдокод

Функция рекурсия(строка, позиция, результат):  
    если позиция == длина(строка):  
        добавить строку в результат  
        вернуть  
  
    для i от позиция до длина(строка):  
        поменять местами строка[позиция] и строка[i]  
        рекурсия(строка, позиция + 1, результат)  
        поменять местами строка[позиция] и строка[i] обратно  
  
Функция решить(строка):  
    результат = пустой список  
    рекурсия(список(строка), 0, результат)  
    вернуть результат

Реализация на Python

Аннотация:  
backtrack - рекурсивная функция, реализующая метод перебора с возвратом для нахождения всех перестановок строки  
s - входная строка, для которой необходимо найти все перестановки  
pos - текущая позиция в строке, с которой производится обмен символов  
result - список для хранения всех найденных перестановок  
solve - функция для нахождения всех возможных перестановок символов в строке

def backtrack(s, pos, result):  
    if pos == len(s):  
        result.append(''.join(s))  
        return  
  
    for i in range(pos, len(s)):  
        s[pos], s[i] = s[i], s[pos]  
        backtrack(s, pos + 1, result)  
        s[pos], s[i] = s[i], s[pos]  
  
def solve(s):  
    result = []  
    backtrack(list(s), 0, result)  
    return result

Олимпиадная реализация на C++

Аннотация:  
typedef - переопределение имени типа данных  
permute - рекурсивная функция, реализующая метод перебора с возвратом для нахождения всех перестановок строки  
s - входная строка, для которой необходимо найти все перестановки  
pos - текущая позиция в строке, с которой производится обмен символов  
res - список для хранения всех найденных перестановок  
solve - функция для нахождения всех возможных перестановок символов в строке

typedef vector<string> vs;  
  
void permute(string& s, int pos, vs& res) {  
    if (pos == s.size()) {  
        res.push_back(s);  
        return;  
    }  
  
    for (int i = pos; i < s.size(); ++i) {  
        swap(s[pos], s[i]);  
        permute(s, pos + 1, res);  
        swap(s[pos], s[i]);  
    }  
}  
  
vs solve(const string& s) {  
    vs res;  
    string s_copy = s;  
    permute(s_copy, 0, res);  
    return res;  
}

Продуктовая реализация на C++

Аннотация:  
backtrack - рекурсивная функция, реализующая метод перебора с возвратом для нахождения всех перестановок строки  
s - входная строка, для которой необходимо найти все перестановки  
pos - текущая позиция в строке, с которой производится обмен символов  
result - список для хранения всех найденных перестановок  
solve - функция для нахождения всех возможных перестановок символов в строке

using namespace std;  
  
void backtrack(string& s, int pos, vector<string>& result) {  
  if (pos == s.size()) {  
    result.push_back(s);  
    return;  
  }  
  
  for (int i = pos; i < s.size(); ++i) {  
    swap(s[pos], s[i]);  
    backtrack(s, pos + 1, result);  
    swap(s[pos], s[i]);  
  }  
}  
  
vector<string> solve(string s) {  
  vector<string> result;  
  backtrack(s, 0, result);  
  return result;  
}