Перейти к содержанию

13.3   Задача о сумме подмножеств

13.3.1   Случай без повторяющихся элементов

Question

Дан массив положительных целых чисел nums и целое положительное значение target . Найдите все возможные комбинации, сумма элементов которых равна target . Во входном массиве нет повторяющихся элементов, и каждый элемент можно выбирать неограниченное число раз. Верните эти комбинации в виде списка; в результате не должно быть повторяющихся комбинаций.

Например, для входного множества \(\{3, 4, 5\}\) и целевого значения \(9\) решениями будут \(\{3, 3, 3\}\) и \(\{4, 5\}\) . При этом нужно обратить внимание на два обстоятельства.

  • Элементы входного множества можно выбирать повторно неограниченное число раз.
  • Подмножество не различает порядок элементов, поэтому \(\{4, 5\}\) и \(\{5, 4\}\) считаются одним и тем же подмножеством.

1.   Отталкиваемся от решения задачи о перестановках

Как и в задаче о перестановках, можно представлять построение подмножеств как результат последовательности выборов и во время выбора динамически обновлять "сумму элементов"; когда эта сумма становится равной target , соответствующее подмножество записывается в список результатов.

Однако в отличие от задачи о перестановках в этой задаче элементы множества можно выбирать неограниченное число раз, поэтому нам не нужен булев список selected для записи того, был ли выбран элемент. Можно слегка изменить код для перестановок и получить первоначальную версию решения:

subset_sum_i_naive.py
def backtrack(
    state: list[int],
    target: int,
    total: int,
    choices: list[int],
    res: list[list[int]],
):
    """Алгоритм бэктрекинга: сумма подмножеств I"""
    # Если сумма подмножества равна target, записать решение
    if total == target:
        res.append(list(state))
        return
    # Перебор всех вариантов выбора
    for i in range(len(choices)):
        # Отсечение: если сумма подмножества превышает target, пропустить этот выбор
        if total + choices[i] > target:
            continue
        # Попытка: сделать выбор и обновить элемент и total
        state.append(choices[i])
        # Перейти к следующему выбору
        backtrack(state, target, total + choices[i], choices, res)
        # Откат: отменить выбор и восстановить предыдущее состояние
        state.pop()

def subset_sum_i_naive(nums: list[int], target: int) -> list[list[int]]:
    """Решить задачу суммы подмножеств I (с повторяющимися подмножествами)"""
    state = []  # Состояние (подмножество)
    total = 0  # Сумма подмножеств
    res = []  # Список результатов (список подмножеств)
    backtrack(state, target, total, nums, res)
    return res
subset_sum_i_naive.cpp
/* Алгоритм бэктрекинга: сумма подмножеств I */
void backtrack(vector<int> &state, int target, int total, vector<int> &choices, vector<vector<int>> &res) {
    // Если сумма подмножества равна target, записать решение
    if (total == target) {
        res.push_back(state);
        return;
    }
    // Перебор всех вариантов выбора
    for (size_t i = 0; i < choices.size(); i++) {
        // Отсечение: если сумма подмножества превышает target, пропустить этот выбор
        if (total + choices[i] > target) {
            continue;
        }
        // Попытка: сделать выбор и обновить элемент и total
        state.push_back(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target, total + choices[i], choices, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.pop_back();
    }
}

/* Решить задачу суммы подмножеств I (с повторяющимися подмножествами) */
vector<vector<int>> subsetSumINaive(vector<int> &nums, int target) {
    vector<int> state;       // Состояние (подмножество)
    int total = 0;           // Сумма подмножеств
    vector<vector<int>> res; // Список результатов (список подмножеств)
    backtrack(state, target, total, nums, res);
    return res;
}
subset_sum_i_naive.java
/* Алгоритм бэктрекинга: сумма подмножеств I */
void backtrack(List<Integer> state, int target, int total, int[] choices, List<List<Integer>> res) {
    // Если сумма подмножества равна target, записать решение
    if (total == target) {
        res.add(new ArrayList<>(state));
        return;
    }
    // Перебор всех вариантов выбора
    for (int i = 0; i < choices.length; i++) {
        // Отсечение: если сумма подмножества превышает target, пропустить этот выбор
        if (total + choices[i] > target) {
            continue;
        }
        // Попытка: сделать выбор и обновить элемент и total
        state.add(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target, total + choices[i], choices, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.remove(state.size() - 1);
    }
}

/* Решить задачу суммы подмножеств I (с повторяющимися подмножествами) */
List<List<Integer>> subsetSumINaive(int[] nums, int target) {
    List<Integer> state = new ArrayList<>(); // Состояние (подмножество)
    int total = 0; // Сумма подмножеств
    List<List<Integer>> res = new ArrayList<>(); // Список результатов (список подмножеств)
    backtrack(state, target, total, nums, res);
    return res;
}
subset_sum_i_naive.cs
/* Алгоритм бэктрекинга: сумма подмножеств I */
void Backtrack(List<int> state, int target, int total, int[] choices, List<List<int>> res) {
    // Если сумма подмножества равна target, записать решение
    if (total == target) {
        res.Add(new List<int>(state));
        return;
    }
    // Перебор всех вариантов выбора
    for (int i = 0; i < choices.Length; i++) {
        // Отсечение: если сумма подмножества превышает target, пропустить этот выбор
        if (total + choices[i] > target) {
            continue;
        }
        // Попытка: сделать выбор и обновить элемент и total
        state.Add(choices[i]);
        // Перейти к следующему выбору
        Backtrack(state, target, total + choices[i], choices, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.RemoveAt(state.Count - 1);
    }
}

/* Решить задачу суммы подмножеств I (с повторяющимися подмножествами) */
List<List<int>> SubsetSumINaive(int[] nums, int target) {
    List<int> state = []; // Состояние (подмножество)
    int total = 0; // Сумма подмножеств
    List<List<int>> res = []; // Список результатов (список подмножеств)
    Backtrack(state, target, total, nums, res);
    return res;
}
subset_sum_i_naive.go
/* Алгоритм бэктрекинга: сумма подмножеств I */
func backtrackSubsetSumINaive(total, target int, state, choices *[]int, res *[][]int) {
    // Если сумма подмножества равна target, записать решение
    if target == total {
        newState := append([]int{}, *state...)
        *res = append(*res, newState)
        return
    }
    // Перебор всех вариантов выбора
    for i := 0; i < len(*choices); i++ {
        // Отсечение: если сумма подмножества превышает target, пропустить этот выбор
        if total+(*choices)[i] > target {
            continue
        }
        // Попытка: сделать выбор и обновить элемент и total
        *state = append(*state, (*choices)[i])
        // Перейти к следующему выбору
        backtrackSubsetSumINaive(total+(*choices)[i], target, state, choices, res)
        // Откат: отменить выбор и восстановить предыдущее состояние
        *state = (*state)[:len(*state)-1]
    }
}

/* Решить задачу суммы подмножеств I (с повторяющимися подмножествами) */
func subsetSumINaive(nums []int, target int) [][]int {
    state := make([]int, 0) // Состояние (подмножество)
    total := 0              // Сумма подмножеств
    res := make([][]int, 0) // Список результатов (список подмножеств)
    backtrackSubsetSumINaive(total, target, &state, &nums, &res)
    return res
}
subset_sum_i_naive.swift
/* Алгоритм бэктрекинга: сумма подмножеств I */
func backtrack(state: inout [Int], target: Int, total: Int, choices: [Int], res: inout [[Int]]) {
    // Если сумма подмножества равна target, записать решение
    if total == target {
        res.append(state)
        return
    }
    // Перебор всех вариантов выбора
    for i in choices.indices {
        // Отсечение: если сумма подмножества превышает target, пропустить этот выбор
        if total + choices[i] > target {
            continue
        }
        // Попытка: сделать выбор и обновить элемент и total
        state.append(choices[i])
        // Перейти к следующему выбору
        backtrack(state: &state, target: target, total: total + choices[i], choices: choices, res: &res)
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.removeLast()
    }
}

/* Решить задачу суммы подмножеств I (с повторяющимися подмножествами) */
func subsetSumINaive(nums: [Int], target: Int) -> [[Int]] {
    var state: [Int] = [] // Состояние (подмножество)
    let total = 0 // Сумма подмножеств
    var res: [[Int]] = [] // Список результатов (список подмножеств)
    backtrack(state: &state, target: target, total: total, choices: nums, res: &res)
    return res
}
subset_sum_i_naive.js
/* Алгоритм бэктрекинга: сумма подмножеств I */
function backtrack(state, target, total, choices, res) {
    // Если сумма подмножества равна target, записать решение
    if (total === target) {
        res.push([...state]);
        return;
    }
    // Перебор всех вариантов выбора
    for (let i = 0; i < choices.length; i++) {
        // Отсечение: если сумма подмножества превышает target, пропустить этот выбор
        if (total + choices[i] > target) {
            continue;
        }
        // Попытка: сделать выбор и обновить элемент и total
        state.push(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target, total + choices[i], choices, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.pop();
    }
}

/* Решить задачу суммы подмножеств I (с повторяющимися подмножествами) */
function subsetSumINaive(nums, target) {
    const state = []; // Состояние (подмножество)
    const total = 0; // Сумма подмножеств
    const res = []; // Список результатов (список подмножеств)
    backtrack(state, target, total, nums, res);
    return res;
}
subset_sum_i_naive.ts
/* Алгоритм бэктрекинга: сумма подмножеств I */
function backtrack(
    state: number[],
    target: number,
    total: number,
    choices: number[],
    res: number[][]
): void {
    // Если сумма подмножества равна target, записать решение
    if (total === target) {
        res.push([...state]);
        return;
    }
    // Перебор всех вариантов выбора
    for (let i = 0; i < choices.length; i++) {
        // Отсечение: если сумма подмножества превышает target, пропустить этот выбор
        if (total + choices[i] > target) {
            continue;
        }
        // Попытка: сделать выбор и обновить элемент и total
        state.push(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target, total + choices[i], choices, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.pop();
    }
}

/* Решить задачу суммы подмножеств I (с повторяющимися подмножествами) */
function subsetSumINaive(nums: number[], target: number): number[][] {
    const state = []; // Состояние (подмножество)
    const total = 0; // Сумма подмножеств
    const res = []; // Список результатов (список подмножеств)
    backtrack(state, target, total, nums, res);
    return res;
}
subset_sum_i_naive.dart
/* Алгоритм бэктрекинга: сумма подмножеств I */
void backtrack(
  List<int> state,
  int target,
  int total,
  List<int> choices,
  List<List<int>> res,
) {
  // Если сумма подмножества равна target, записать решение
  if (total == target) {
    res.add(List.from(state));
    return;
  }
  // Перебор всех вариантов выбора
  for (int i = 0; i < choices.length; i++) {
    // Отсечение: если сумма подмножества превышает target, пропустить этот выбор
    if (total + choices[i] > target) {
      continue;
    }
    // Попытка: сделать выбор и обновить элемент и total
    state.add(choices[i]);
    // Перейти к следующему выбору
    backtrack(state, target, total + choices[i], choices, res);
    // Откат: отменить выбор и восстановить предыдущее состояние
    state.removeLast();
  }
}

/* Решить задачу суммы подмножеств I (с повторяющимися подмножествами) */
List<List<int>> subsetSumINaive(List<int> nums, int target) {
  List<int> state = []; // Состояние (подмножество)
  int total = 0; // Сумма элементов
  List<List<int>> res = []; // Список результатов (список подмножеств)
  backtrack(state, target, total, nums, res);
  return res;
}
subset_sum_i_naive.rs
/* Алгоритм бэктрекинга: сумма подмножеств I */
fn backtrack(
    state: &mut Vec<i32>,
    target: i32,
    total: i32,
    choices: &[i32],
    res: &mut Vec<Vec<i32>>,
) {
    // Если сумма подмножества равна target, записать решение
    if total == target {
        res.push(state.clone());
        return;
    }
    // Перебор всех вариантов выбора
    for i in 0..choices.len() {
        // Отсечение: если сумма подмножества превышает target, пропустить этот выбор
        if total + choices[i] > target {
            continue;
        }
        // Попытка: сделать выбор и обновить элемент и total
        state.push(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target, total + choices[i], choices, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.pop();
    }
}

/* Решить задачу суммы подмножеств I (с повторяющимися подмножествами) */
fn subset_sum_i_naive(nums: &[i32], target: i32) -> Vec<Vec<i32>> {
    let mut state = Vec::new(); // Состояние (подмножество)
    let total = 0; // Сумма подмножеств
    let mut res = Vec::new(); // Список результатов (список подмножеств)
    backtrack(&mut state, target, total, nums, &mut res);
    res
}
subset_sum_i_naive.c
/* Алгоритм бэктрекинга: сумма подмножеств I */
void backtrack(int target, int total, int *choices, int choicesSize) {
    // Если сумма подмножества равна target, записать решение
    if (total == target) {
        for (int i = 0; i < stateSize; i++) {
            res[resSize][i] = state[i];
        }
        resColSizes[resSize++] = stateSize;
        return;
    }
    // Перебор всех вариантов выбора
    for (int i = 0; i < choicesSize; i++) {
        // Отсечение: если сумма подмножества превышает target, пропустить этот выбор
        if (total + choices[i] > target) {
            continue;
        }
        // Попытка: сделать выбор и обновить элемент и total
        state[stateSize++] = choices[i];
        // Перейти к следующему выбору
        backtrack(target, total + choices[i], choices, choicesSize);
        // Откат: отменить выбор и восстановить предыдущее состояние
        stateSize--;
    }
}

/* Решить задачу суммы подмножеств I (с повторяющимися подмножествами) */
void subsetSumINaive(int *nums, int numsSize, int target) {
    resSize = 0; // Инициализировать число решений нулем
    backtrack(target, 0, nums, numsSize);
}
subset_sum_i_naive.kt
/* Алгоритм бэктрекинга: сумма подмножеств I */
fun backtrack(
    state: MutableList<Int>,
    target: Int,
    total: Int,
    choices: IntArray,
    res: MutableList<MutableList<Int>?>
) {
    // Если сумма подмножества равна target, записать решение
    if (total == target) {
        res.add(state.toMutableList())
        return
    }
    // Перебор всех вариантов выбора
    for (i in choices.indices) {
        // Отсечение: если сумма подмножества превышает target, пропустить этот выбор
        if (total + choices[i] > target) {
            continue
        }
        // Попытка: сделать выбор и обновить элемент и total
        state.add(choices[i])
        // Перейти к следующему выбору
        backtrack(state, target, total + choices[i], choices, res)
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.removeAt(state.size - 1)
    }
}

/* Решить задачу суммы подмножеств I (с повторяющимися подмножествами) */
fun subsetSumINaive(nums: IntArray, target: Int): MutableList<MutableList<Int>?> {
    val state = mutableListOf<Int>() // Состояние (подмножество)
    val total = 0 // Сумма подмножеств
    val res = mutableListOf<MutableList<Int>?>() // Список результатов (список подмножеств)
    backtrack(state, target, total, nums, res)
    return res
}
subset_sum_i_naive.rb
### Алгоритм бэктрекинга: сумма подмножеств I ###
def backtrack(state, target, total, choices, res)
  # Если сумма подмножества равна target, записать решение
  if total == target
    res << state.dup
    return
  end

  # Перебор всех вариантов выбора
  for i in 0...choices.length
    # Отсечение: если сумма подмножества превышает target, пропустить этот выбор
    next if total + choices[i] > target
    # Попытка: сделать выбор и обновить элемент и total
    state << choices[i]
    # Перейти к следующему выбору
    backtrack(state, target, total + choices[i], choices, res)
    # Откат: отменить выбор и восстановить предыдущее состояние
    state.pop
  end
end

### Алгоритм бэктрекинга: сумма подмножеств I ###
def backtrack(state, target, total, choices, res)
  # Если сумма подмножества равна target, записать решение
  if total == target
    res << state.dup
    return
  end

  # Перебор всех вариантов выбора
  for i in 0...choices.length
    # Отсечение: если сумма подмножества превышает target, пропустить этот выбор
    next if total + choices[i] > target
    # Попытка: сделать выбор и обновить элемент и total
    state << choices[i]
    # Перейти к следующему выбору
    backtrack(state, target, total + choices[i], choices, res)
    # Откат: отменить выбор и восстановить предыдущее состояние
    state.pop
  end
end

# ## Решить задачу суммы подмножеств I (с повторяющимися подмножествами) ###
def subset_sum_i_naive(nums, target)
  state = [] # Состояние (подмножество)
  total = 0 # Сумма подмножеств
  res = [] # Список результатов (список подмножеств)
  backtrack(state, target, total, nums, res)
  res
end
Визуализация кода

Если подать на этот код массив \([3, 4, 5]\) и целевое значение \(9\) , то на выходе мы получим \([3, 3, 3], [4, 5], [5, 4]\) . Хотя все подмножества с суммой \(9\) успешно найдены, среди них все же присутствуют дубликаты: \([4, 5]\) и \([5, 4]\) .

Причина в том, что процесс поиска различает порядок выбора, тогда как для подмножеств порядок не важен. Как показано на рисунке 13-10, сначала выбрать \(4\) , а затем \(5\) , и сначала выбрать \(5\) , а затем \(4\) - это разные ветви поиска, но им соответствует одно и то же подмножество.

Поиск подмножеств и обрезка по выходу за границу

Рисунок 13-10   Поиск подмножеств и обрезка по выходу за границу

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

  • Когда массив содержит много элементов, а особенно когда target велик, процесс поиска порождает огромное число повторяющихся подмножеств.
  • Сравнение подмножеств (то есть массивов) само по себе довольно затратно: сначала приходится сортировать массивы, а затем поэлементно сравнивать их.

2.   Обрезка повторяющихся подмножеств

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

  1. Если в первом и втором раундах выбрать соответственно \(3\) и \(4\) , то будут сгенерированы все подмножества, содержащие эти два элемента, и их можно обозначить как \([3, 4, \dots]\) .
  2. После этого, если в первом раунде выбрать \(4\) , то во втором раунде нужно пропустить \(3\) , потому что подмножества \([4, 3, \dots]\) полностью дублируют подмножества, уже построенные на шаге 1. .

Во время поиска выборы на каждом уровне пробуются по одному слева направо, поэтому чем правее ветвь, тем больше ветвей оказывается отсечено.

  1. В первых двух раундах выбираются \(3\) и \(5\) , что дает подмножества \([3, 5, \dots]\) .
  2. В первых двух раундах выбираются \(4\) и \(5\) , что дает подмножества \([4, 5, \dots]\) .
  3. Если же в первом раунде выбрать \(5\) , то во втором раунде нужно пропустить \(3\) и \(4\) , потому что подмножества \([5, 3, \dots]\) и \([5, 4, \dots]\) полностью дублируют случаи, описанные в шагах 1. и 2. .

Повторяющиеся подмножества из-за разного порядка выбора

Рисунок 13-11   Повторяющиеся подмножества из-за разного порядка выбора

В общем виде, если входной массив имеет вид \([x_1, x_2, \dots, x_n]\) , а последовательность выборов в ходе поиска равна \([x_{i_1}, x_{i_2}, \dots, x_{i_m}]\) , то она должна удовлетворять условию \(i_1 \leq i_2 \leq \dots \leq i_m\) ; все последовательности выборов, не удовлетворяющие этому условию, приводят к дубликатам и должны отсекаться.

3.   Реализация кода

Чтобы реализовать такую обрезку, инициализируем переменную start , которая будет указывать начальную точку обхода. После выбора элемента \(x_i\) следующий раунд начинается с индекса \(i\). Благодаря этому последовательность выборов всегда удовлетворяет условию \(i_1 \leq i_2 \leq \dots \leq i_m\) , а значит, каждое подмножество создается только один раз.

Помимо этого, мы внесем в код еще два улучшения.

  • Перед началом поиска отсортируем массив nums . Тогда при обходе всех вариантов можно сразу прервать цикл, как только сумма подмножества превысит target , потому что все последующие элементы будут еще больше и их сумма тоже превысит target .
  • Откажемся от отдельной переменной суммы total и будем учитывать сумму через вычитание из target ; когда target станет равным \(0\) , решение фиксируется.
subset_sum_i.py
def backtrack(
    state: list[int], target: int, choices: list[int], start: int, res: list[list[int]]
):
    """Алгоритм бэктрекинга: сумма подмножеств I"""
    # Если сумма подмножества равна target, записать решение
    if target == 0:
        res.append(list(state))
        return
    # Обойти все варианты выбора
    # Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    for i in range(start, len(choices)):
        # Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        # Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if target - choices[i] < 0:
            break
        # Попытка: сделать выбор и обновить target и start
        state.append(choices[i])
        # Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i, res)
        # Откат: отменить выбор и восстановить предыдущее состояние
        state.pop()

def subset_sum_i(nums: list[int], target: int) -> list[list[int]]:
    """Решить задачу суммы подмножеств I"""
    state = []  # Состояние (подмножество)
    nums.sort()  # Отсортировать nums
    start = 0  # Стартовая вершина обхода
    res = []  # Список результатов (список подмножеств)
    backtrack(state, target, nums, start, res)
    return res
subset_sum_i.cpp
/* Алгоритм бэктрекинга: сумма подмножеств I */
void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
    // Если сумма подмножества равна target, записать решение
    if (target == 0) {
        res.push_back(state);
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    for (int i = start; i < choices.size(); i++) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if (target - choices[i] < 0) {
            break;
        }
        // Попытка: сделать выбор и обновить target и start
        state.push_back(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.pop_back();
    }
}

/* Решить задачу суммы подмножеств I */
vector<vector<int>> subsetSumI(vector<int> &nums, int target) {
    vector<int> state;              // Состояние (подмножество)
    sort(nums.begin(), nums.end()); // Отсортировать nums
    int start = 0;                  // Стартовая вершина обхода
    vector<vector<int>> res;        // Список результатов (список подмножеств)
    backtrack(state, target, nums, start, res);
    return res;
}
subset_sum_i.java
/* Алгоритм бэктрекинга: сумма подмножеств I */
void backtrack(List<Integer> state, int target, int[] choices, int start, List<List<Integer>> res) {
    // Если сумма подмножества равна target, записать решение
    if (target == 0) {
        res.add(new ArrayList<>(state));
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    for (int i = start; i < choices.length; i++) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if (target - choices[i] < 0) {
            break;
        }
        // Попытка: сделать выбор и обновить target и start
        state.add(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.remove(state.size() - 1);
    }
}

/* Решить задачу суммы подмножеств I */
List<List<Integer>> subsetSumI(int[] nums, int target) {
    List<Integer> state = new ArrayList<>(); // Состояние (подмножество)
    Arrays.sort(nums); // Отсортировать nums
    int start = 0; // Стартовая вершина обхода
    List<List<Integer>> res = new ArrayList<>(); // Список результатов (список подмножеств)
    backtrack(state, target, nums, start, res);
    return res;
}
subset_sum_i.cs
/* Алгоритм бэктрекинга: сумма подмножеств I */
void Backtrack(List<int> state, int target, int[] choices, int start, List<List<int>> res) {
    // Если сумма подмножества равна target, записать решение
    if (target == 0) {
        res.Add(new List<int>(state));
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    for (int i = start; i < choices.Length; i++) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if (target - choices[i] < 0) {
            break;
        }
        // Попытка: сделать выбор и обновить target и start
        state.Add(choices[i]);
        // Перейти к следующему выбору
        Backtrack(state, target - choices[i], choices, i, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.RemoveAt(state.Count - 1);
    }
}

/* Решить задачу суммы подмножеств I */
List<List<int>> SubsetSumI(int[] nums, int target) {
    List<int> state = []; // Состояние (подмножество)
    Array.Sort(nums); // Отсортировать nums
    int start = 0; // Стартовая вершина обхода
    List<List<int>> res = []; // Список результатов (список подмножеств)
    Backtrack(state, target, nums, start, res);
    return res;
}
subset_sum_i.go
/* Алгоритм бэктрекинга: сумма подмножеств I */
func backtrackSubsetSumI(start, target int, state, choices *[]int, res *[][]int) {
    // Если сумма подмножества равна target, записать решение
    if target == 0 {
        newState := append([]int{}, *state...)
        *res = append(*res, newState)
        return
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    for i := start; i < len(*choices); i++ {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if target-(*choices)[i] < 0 {
            break
        }
        // Попытка: сделать выбор и обновить target и start
        *state = append(*state, (*choices)[i])
        // Перейти к следующему выбору
        backtrackSubsetSumI(i, target-(*choices)[i], state, choices, res)
        // Откат: отменить выбор и восстановить предыдущее состояние
        *state = (*state)[:len(*state)-1]
    }
}

/* Решить задачу суммы подмножеств I */
func subsetSumI(nums []int, target int) [][]int {
    state := make([]int, 0) // Состояние (подмножество)
    sort.Ints(nums)         // Отсортировать nums
    start := 0              // Стартовая вершина обхода
    res := make([][]int, 0) // Список результатов (список подмножеств)
    backtrackSubsetSumI(start, target, &state, &nums, &res)
    return res
}
subset_sum_i.swift
/* Алгоритм бэктрекинга: сумма подмножеств I */
func backtrack(state: inout [Int], target: Int, choices: [Int], start: Int, res: inout [[Int]]) {
    // Если сумма подмножества равна target, записать решение
    if target == 0 {
        res.append(state)
        return
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    for i in choices.indices.dropFirst(start) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if target - choices[i] < 0 {
            break
        }
        // Попытка: сделать выбор и обновить target и start
        state.append(choices[i])
        // Перейти к следующему выбору
        backtrack(state: &state, target: target - choices[i], choices: choices, start: i, res: &res)
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.removeLast()
    }
}

/* Решить задачу суммы подмножеств I */
func subsetSumI(nums: [Int], target: Int) -> [[Int]] {
    var state: [Int] = [] // Состояние (подмножество)
    let nums = nums.sorted() // Отсортировать nums
    let start = 0 // Стартовая вершина обхода
    var res: [[Int]] = [] // Список результатов (список подмножеств)
    backtrack(state: &state, target: target, choices: nums, start: start, res: &res)
    return res
}
subset_sum_i.js
/* Алгоритм бэктрекинга: сумма подмножеств I */
function backtrack(state, target, choices, start, res) {
    // Если сумма подмножества равна target, записать решение
    if (target === 0) {
        res.push([...state]);
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    for (let i = start; i < choices.length; i++) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if (target - choices[i] < 0) {
            break;
        }
        // Попытка: сделать выбор и обновить target и start
        state.push(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.pop();
    }
}

/* Решить задачу суммы подмножеств I */
function subsetSumI(nums, target) {
    const state = []; // Состояние (подмножество)
    nums.sort((a, b) => a - b); // Отсортировать nums
    const start = 0; // Стартовая вершина обхода
    const res = []; // Список результатов (список подмножеств)
    backtrack(state, target, nums, start, res);
    return res;
}
subset_sum_i.ts
/* Алгоритм бэктрекинга: сумма подмножеств I */
function backtrack(
    state: number[],
    target: number,
    choices: number[],
    start: number,
    res: number[][]
): void {
    // Если сумма подмножества равна target, записать решение
    if (target === 0) {
        res.push([...state]);
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    for (let i = start; i < choices.length; i++) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if (target - choices[i] < 0) {
            break;
        }
        // Попытка: сделать выбор и обновить target и start
        state.push(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.pop();
    }
}

/* Решить задачу суммы подмножеств I */
function subsetSumI(nums: number[], target: number): number[][] {
    const state = []; // Состояние (подмножество)
    nums.sort((a, b) => a - b); // Отсортировать nums
    const start = 0; // Стартовая вершина обхода
    const res = []; // Список результатов (список подмножеств)
    backtrack(state, target, nums, start, res);
    return res;
}
subset_sum_i.dart
/* Алгоритм бэктрекинга: сумма подмножеств I */
void backtrack(
  List<int> state,
  int target,
  List<int> choices,
  int start,
  List<List<int>> res,
) {
  // Если сумма подмножества равна target, записать решение
  if (target == 0) {
    res.add(List.from(state));
    return;
  }
  // Обойти все варианты выбора
  // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
  for (int i = start; i < choices.length; i++) {
    // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
    // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
    if (target - choices[i] < 0) {
      break;
    }
    // Попытка: сделать выбор и обновить target и start
    state.add(choices[i]);
    // Перейти к следующему выбору
    backtrack(state, target - choices[i], choices, i, res);
    // Откат: отменить выбор и восстановить предыдущее состояние
    state.removeLast();
  }
}

/* Решить задачу суммы подмножеств I */
List<List<int>> subsetSumI(List<int> nums, int target) {
  List<int> state = []; // Состояние (подмножество)
  nums.sort(); // Отсортировать nums
  int start = 0; // Стартовая вершина обхода
  List<List<int>> res = []; // Список результатов (список подмножеств)
  backtrack(state, target, nums, start, res);
  return res;
}
subset_sum_i.rs
/* Алгоритм бэктрекинга: сумма подмножеств I */
fn backtrack(
    state: &mut Vec<i32>,
    target: i32,
    choices: &[i32],
    start: usize,
    res: &mut Vec<Vec<i32>>,
) {
    // Если сумма подмножества равна target, записать решение
    if target == 0 {
        res.push(state.clone());
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    for i in start..choices.len() {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if target - choices[i] < 0 {
            break;
        }
        // Попытка: сделать выбор и обновить target и start
        state.push(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.pop();
    }
}

/* Решить задачу суммы подмножеств I */
fn subset_sum_i(nums: &mut [i32], target: i32) -> Vec<Vec<i32>> {
    let mut state = Vec::new(); // Состояние (подмножество)
    nums.sort(); // Отсортировать nums
    let start = 0; // Стартовая вершина обхода
    let mut res = Vec::new(); // Список результатов (список подмножеств)
    backtrack(&mut state, target, nums, start, &mut res);
    res
}
subset_sum_i.c
/* Алгоритм бэктрекинга: сумма подмножеств I */
void backtrack(int target, int *choices, int choicesSize, int start) {
    // Если сумма подмножества равна target, записать решение
    if (target == 0) {
        for (int i = 0; i < stateSize; ++i) {
            res[resSize][i] = state[i];
        }
        resColSizes[resSize++] = stateSize;
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    for (int i = start; i < choicesSize; i++) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if (target - choices[i] < 0) {
            break;
        }
        // Попытка: сделать выбор и обновить target и start
        state[stateSize] = choices[i];
        stateSize++;
        // Перейти к следующему выбору
        backtrack(target - choices[i], choices, choicesSize, i);
        // Откат: отменить выбор и восстановить предыдущее состояние
        stateSize--;
    }
}

/* Решить задачу суммы подмножеств I */
void subsetSumI(int *nums, int numsSize, int target) {
    qsort(nums, numsSize, sizeof(int), cmp); // Отсортировать nums
    int start = 0;                           // Стартовая вершина обхода
    backtrack(target, nums, numsSize, start);
}
subset_sum_i.kt
/* Алгоритм бэктрекинга: сумма подмножеств I */
fun backtrack(
    state: MutableList<Int>,
    target: Int,
    choices: IntArray,
    start: Int,
    res: MutableList<MutableList<Int>?>
) {
    // Если сумма подмножества равна target, записать решение
    if (target == 0) {
        res.add(state.toMutableList())
        return
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    for (i in start..<choices.size) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if (target - choices[i] < 0) {
            break
        }
        // Попытка: сделать выбор и обновить target и start
        state.add(choices[i])
        // Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i, res)
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.removeAt(state.size - 1)
    }
}

/* Решить задачу суммы подмножеств I */
fun subsetSumI(nums: IntArray, target: Int): MutableList<MutableList<Int>?> {
    val state = mutableListOf<Int>() // Состояние (подмножество)
    nums.sort() // Отсортировать nums
    val start = 0 // Стартовая вершина обхода
    val res = mutableListOf<MutableList<Int>?>() // Список результатов (список подмножеств)
    backtrack(state, target, nums, start, res)
    return res
}
subset_sum_i.rb
### Алгоритм бэктрекинга: сумма подмножеств I ###
def backtrack(state, target, choices, start, res)
  # Если сумма подмножества равна target, записать решение
  if target.zero?
    res << state.dup
    return
  end
  # Обойти все варианты выбора
  # Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
  for i in start...choices.length
    # Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
    # Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
    break if target - choices[i] < 0
    # Попытка: сделать выбор и обновить target и start
    state << choices[i]
    # Перейти к следующему выбору
    backtrack(state, target - choices[i], choices, i, res)
    # Откат: отменить выбор и восстановить предыдущее состояние
    state.pop
  end
end

### Решить задачу суммы подмножеств I ###
def subset_sum_i(nums, target)
  state = [] # Состояние (подмножество)
  nums.sort! # Отсортировать nums
  start = 0 # Стартовая вершина обхода
  res = [] # Список результатов (список подмножеств)
  backtrack(state, target, nums, start, res)
  res
end
Визуализация кода

На рисунке 13-12 показан полный процесс backtracking для массива \([3, 4, 5]\) и целевого значения \(9\) .

Процесс backtracking для задачи о сумме подмножеств I

Рисунок 13-12   Процесс backtracking для задачи о сумме подмножеств I

13.3.2   Учет повторяющихся элементов

Question

Дан массив положительных целых чисел nums и целое положительное значение target . Найдите все возможные комбинации, сумма элементов которых равна target . Во входном массиве могут присутствовать повторяющиеся элементы, и каждый элемент разрешено выбирать только один раз. Верните эти комбинации в виде списка; в результате не должно быть повторяющихся комбинаций.

По сравнению с предыдущей задачей во входном массиве теперь могут присутствовать повторяющиеся элементы, и это создает новую проблему. Например, если дан массив \([4, \hat{4}, 5]\) и целевое значение \(9\) , то существующий код вернет результат \([4, 5], [\hat{4}, 5]\) , то есть с повторяющимся подмножеством.

Причина появления дублей в том, что равные элементы выбираются несколько раз в одном и том же раунде. На рисунке 13-13 в первом раунде существует три варианта выбора, и два из них равны \(4\) ; из-за этого появляются две дублирующиеся ветви поиска и, соответственно, повторяющиеся подмножества. Точно так же два элемента \(4\) во втором раунде тоже порождают дубликаты.

Повторяющиеся подмножества из-за равных элементов

Рисунок 13-13   Повторяющиеся подмножества из-за равных элементов

1.   Обрезка равных элементов

Чтобы решить эту проблему, нужно ограничить выбор равных элементов так, чтобы в каждом раунде каждый из них выбирался только один раз. Реализуется это довольно изящно: поскольку массив отсортирован, равные элементы стоят рядом. Значит, если в текущем раунде текущий элемент равен соседнему слева, то этот вариант уже был рассмотрен, и текущий элемент нужно пропустить.

Одновременно по условию этой задачи каждый элемент массива можно выбрать только один раз. К счастью, это ограничение тоже можно реализовать через переменную start : после выбора элемента \(x_i\) следующий раунд начинается с индекса \(i + 1\) . Так мы одновременно убираем повторяющиеся подмножества и исключаем повторный выбор одного и того же элемента.

2.   Реализация кода

subset_sum_ii.py
def backtrack(
    state: list[int], target: int, choices: list[int], start: int, res: list[list[int]]
):
    """Алгоритм бэктрекинга: сумма подмножеств II"""
    # Если сумма подмножества равна target, записать решение
    if target == 0:
        res.append(list(state))
        return
    # Обойти все варианты выбора
    # Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    # Отсечение 3: начинать обход с start, чтобы избежать повторного выбора одного и того же элемента
    for i in range(start, len(choices)):
        # Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        # Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if target - choices[i] < 0:
            break
        # Отсечение 4: если этот элемент равен элементу слева, значит ветвь поиска повторяется, ее нужно сразу пропустить
        if i > start and choices[i] == choices[i - 1]:
            continue
        # Попытка: сделать выбор и обновить target и start
        state.append(choices[i])
        # Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i + 1, res)
        # Откат: отменить выбор и восстановить предыдущее состояние
        state.pop()

def subset_sum_ii(nums: list[int], target: int) -> list[list[int]]:
    """Решить задачу суммы подмножеств II"""
    state = []  # Состояние (подмножество)
    nums.sort()  # Отсортировать nums
    start = 0  # Стартовая вершина обхода
    res = []  # Список результатов (список подмножеств)
    backtrack(state, target, nums, start, res)
    return res
subset_sum_ii.cpp
/* Алгоритм бэктрекинга: сумма подмножеств II */
void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
    // Если сумма подмножества равна target, записать решение
    if (target == 0) {
        res.push_back(state);
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    // Отсечение 3: начинать обход с start, чтобы избежать повторного выбора одного и того же элемента
    for (int i = start; i < choices.size(); i++) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if (target - choices[i] < 0) {
            break;
        }
        // Отсечение 4: если этот элемент равен элементу слева, значит ветвь поиска повторяется, ее нужно сразу пропустить
        if (i > start && choices[i] == choices[i - 1]) {
            continue;
        }
        // Попытка: сделать выбор и обновить target и start
        state.push_back(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i + 1, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.pop_back();
    }
}

/* Решить задачу суммы подмножеств II */
vector<vector<int>> subsetSumII(vector<int> &nums, int target) {
    vector<int> state;              // Состояние (подмножество)
    sort(nums.begin(), nums.end()); // Отсортировать nums
    int start = 0;                  // Стартовая вершина обхода
    vector<vector<int>> res;        // Список результатов (список подмножеств)
    backtrack(state, target, nums, start, res);
    return res;
}
subset_sum_ii.java
/* Алгоритм бэктрекинга: сумма подмножеств II */
void backtrack(List<Integer> state, int target, int[] choices, int start, List<List<Integer>> res) {
    // Если сумма подмножества равна target, записать решение
    if (target == 0) {
        res.add(new ArrayList<>(state));
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    // Отсечение 3: начинать обход с start, чтобы избежать повторного выбора одного и того же элемента
    for (int i = start; i < choices.length; i++) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if (target - choices[i] < 0) {
            break;
        }
        // Отсечение 4: если этот элемент равен элементу слева, значит ветвь поиска повторяется, ее нужно сразу пропустить
        if (i > start && choices[i] == choices[i - 1]) {
            continue;
        }
        // Попытка: сделать выбор и обновить target и start
        state.add(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i + 1, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.remove(state.size() - 1);
    }
}

/* Решить задачу суммы подмножеств II */
List<List<Integer>> subsetSumII(int[] nums, int target) {
    List<Integer> state = new ArrayList<>(); // Состояние (подмножество)
    Arrays.sort(nums); // Отсортировать nums
    int start = 0; // Стартовая вершина обхода
    List<List<Integer>> res = new ArrayList<>(); // Список результатов (список подмножеств)
    backtrack(state, target, nums, start, res);
    return res;
}
subset_sum_ii.cs
/* Алгоритм бэктрекинга: сумма подмножеств II */
void Backtrack(List<int> state, int target, int[] choices, int start, List<List<int>> res) {
    // Если сумма подмножества равна target, записать решение
    if (target == 0) {
        res.Add(new List<int>(state));
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    // Отсечение 3: начинать обход с start, чтобы избежать повторного выбора одного и того же элемента
    for (int i = start; i < choices.Length; i++) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if (target - choices[i] < 0) {
            break;
        }
        // Отсечение 4: если этот элемент равен элементу слева, значит ветвь поиска повторяется, ее нужно сразу пропустить
        if (i > start && choices[i] == choices[i - 1]) {
            continue;
        }
        // Попытка: сделать выбор и обновить target и start
        state.Add(choices[i]);
        // Перейти к следующему выбору
        Backtrack(state, target - choices[i], choices, i + 1, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.RemoveAt(state.Count - 1);
    }
}

/* Решить задачу суммы подмножеств II */
List<List<int>> SubsetSumII(int[] nums, int target) {
    List<int> state = []; // Состояние (подмножество)
    Array.Sort(nums); // Отсортировать nums
    int start = 0; // Стартовая вершина обхода
    List<List<int>> res = []; // Список результатов (список подмножеств)
    Backtrack(state, target, nums, start, res);
    return res;
}
subset_sum_ii.go
/* Алгоритм бэктрекинга: сумма подмножеств II */
func backtrackSubsetSumII(start, target int, state, choices *[]int, res *[][]int) {
    // Если сумма подмножества равна target, записать решение
    if target == 0 {
        newState := append([]int{}, *state...)
        *res = append(*res, newState)
        return
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    // Отсечение 3: начинать обход с start, чтобы избежать повторного выбора одного и того же элемента
    for i := start; i < len(*choices); i++ {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if target-(*choices)[i] < 0 {
            break
        }
        // Отсечение 4: если этот элемент равен элементу слева, значит ветвь поиска повторяется, ее нужно сразу пропустить
        if i > start && (*choices)[i] == (*choices)[i-1] {
            continue
        }
        // Попытка: сделать выбор и обновить target и start
        *state = append(*state, (*choices)[i])
        // Перейти к следующему выбору
        backtrackSubsetSumII(i+1, target-(*choices)[i], state, choices, res)
        // Откат: отменить выбор и восстановить предыдущее состояние
        *state = (*state)[:len(*state)-1]
    }
}

/* Решить задачу суммы подмножеств II */
func subsetSumII(nums []int, target int) [][]int {
    state := make([]int, 0) // Состояние (подмножество)
    sort.Ints(nums)         // Отсортировать nums
    start := 0              // Стартовая вершина обхода
    res := make([][]int, 0) // Список результатов (список подмножеств)
    backtrackSubsetSumII(start, target, &state, &nums, &res)
    return res
}
subset_sum_ii.swift
/* Алгоритм бэктрекинга: сумма подмножеств II */
func backtrack(state: inout [Int], target: Int, choices: [Int], start: Int, res: inout [[Int]]) {
    // Если сумма подмножества равна target, записать решение
    if target == 0 {
        res.append(state)
        return
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    // Отсечение 3: начинать обход с start, чтобы избежать повторного выбора одного и того же элемента
    for i in choices.indices.dropFirst(start) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if target - choices[i] < 0 {
            break
        }
        // Отсечение 4: если этот элемент равен элементу слева, значит ветвь поиска повторяется, ее нужно сразу пропустить
        if i > start, choices[i] == choices[i - 1] {
            continue
        }
        // Попытка: сделать выбор и обновить target и start
        state.append(choices[i])
        // Перейти к следующему выбору
        backtrack(state: &state, target: target - choices[i], choices: choices, start: i + 1, res: &res)
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.removeLast()
    }
}

/* Решить задачу суммы подмножеств II */
func subsetSumII(nums: [Int], target: Int) -> [[Int]] {
    var state: [Int] = [] // Состояние (подмножество)
    let nums = nums.sorted() // Отсортировать nums
    let start = 0 // Стартовая вершина обхода
    var res: [[Int]] = [] // Список результатов (список подмножеств)
    backtrack(state: &state, target: target, choices: nums, start: start, res: &res)
    return res
}
subset_sum_ii.js
/* Алгоритм бэктрекинга: сумма подмножеств II */
function backtrack(state, target, choices, start, res) {
    // Если сумма подмножества равна target, записать решение
    if (target === 0) {
        res.push([...state]);
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    // Отсечение 3: начинать обход с start, чтобы избежать повторного выбора одного и того же элемента
    for (let i = start; i < choices.length; i++) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if (target - choices[i] < 0) {
            break;
        }
        // Отсечение 4: если этот элемент равен элементу слева, значит ветвь поиска повторяется, ее нужно сразу пропустить
        if (i > start && choices[i] === choices[i - 1]) {
            continue;
        }
        // Попытка: сделать выбор и обновить target и start
        state.push(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i + 1, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.pop();
    }
}

/* Решить задачу суммы подмножеств II */
function subsetSumII(nums, target) {
    const state = []; // Состояние (подмножество)
    nums.sort((a, b) => a - b); // Отсортировать nums
    const start = 0; // Стартовая вершина обхода
    const res = []; // Список результатов (список подмножеств)
    backtrack(state, target, nums, start, res);
    return res;
}
subset_sum_ii.ts
/* Алгоритм бэктрекинга: сумма подмножеств II */
function backtrack(
    state: number[],
    target: number,
    choices: number[],
    start: number,
    res: number[][]
): void {
    // Если сумма подмножества равна target, записать решение
    if (target === 0) {
        res.push([...state]);
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    // Отсечение 3: начинать обход с start, чтобы избежать повторного выбора одного и того же элемента
    for (let i = start; i < choices.length; i++) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if (target - choices[i] < 0) {
            break;
        }
        // Отсечение 4: если этот элемент равен элементу слева, значит ветвь поиска повторяется, ее нужно сразу пропустить
        if (i > start && choices[i] === choices[i - 1]) {
            continue;
        }
        // Попытка: сделать выбор и обновить target и start
        state.push(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i + 1, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.pop();
    }
}

/* Решить задачу суммы подмножеств II */
function subsetSumII(nums: number[], target: number): number[][] {
    const state = []; // Состояние (подмножество)
    nums.sort((a, b) => a - b); // Отсортировать nums
    const start = 0; // Стартовая вершина обхода
    const res = []; // Список результатов (список подмножеств)
    backtrack(state, target, nums, start, res);
    return res;
}
subset_sum_ii.dart
/* Алгоритм бэктрекинга: сумма подмножеств II */
void backtrack(
  List<int> state,
  int target,
  List<int> choices,
  int start,
  List<List<int>> res,
) {
  // Если сумма подмножества равна target, записать решение
  if (target == 0) {
    res.add(List.from(state));
    return;
  }
  // Обойти все варианты выбора
  // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
  // Отсечение 3: начинать обход с start, чтобы избежать повторного выбора одного и того же элемента
  for (int i = start; i < choices.length; i++) {
    // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
    // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
    if (target - choices[i] < 0) {
      break;
    }
    // Отсечение 4: если этот элемент равен элементу слева, значит ветвь поиска повторяется, ее нужно сразу пропустить
    if (i > start && choices[i] == choices[i - 1]) {
      continue;
    }
    // Попытка: сделать выбор и обновить target и start
    state.add(choices[i]);
    // Перейти к следующему выбору
    backtrack(state, target - choices[i], choices, i + 1, res);
    // Откат: отменить выбор и восстановить предыдущее состояние
    state.removeLast();
  }
}

/* Решить задачу суммы подмножеств II */
List<List<int>> subsetSumII(List<int> nums, int target) {
  List<int> state = []; // Состояние (подмножество)
  nums.sort(); // Отсортировать nums
  int start = 0; // Стартовая вершина обхода
  List<List<int>> res = []; // Список результатов (список подмножеств)
  backtrack(state, target, nums, start, res);
  return res;
}
subset_sum_ii.rs
/* Алгоритм бэктрекинга: сумма подмножеств II */
fn backtrack(
    state: &mut Vec<i32>,
    target: i32,
    choices: &[i32],
    start: usize,
    res: &mut Vec<Vec<i32>>,
) {
    // Если сумма подмножества равна target, записать решение
    if target == 0 {
        res.push(state.clone());
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    // Отсечение 3: начинать обход с start, чтобы избежать повторного выбора одного и того же элемента
    for i in start..choices.len() {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if target - choices[i] < 0 {
            break;
        }
        // Отсечение 4: если этот элемент равен элементу слева, значит ветвь поиска повторяется, ее нужно сразу пропустить
        if i > start && choices[i] == choices[i - 1] {
            continue;
        }
        // Попытка: сделать выбор и обновить target и start
        state.push(choices[i]);
        // Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i + 1, res);
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.pop();
    }
}

/* Решить задачу суммы подмножеств II */
fn subset_sum_ii(nums: &mut [i32], target: i32) -> Vec<Vec<i32>> {
    let mut state = Vec::new(); // Состояние (подмножество)
    nums.sort(); // Отсортировать nums
    let start = 0; // Стартовая вершина обхода
    let mut res = Vec::new(); // Список результатов (список подмножеств)
    backtrack(&mut state, target, nums, start, &mut res);
    res
}
subset_sum_ii.c
/* Алгоритм бэктрекинга: сумма подмножеств II */
void backtrack(int target, int *choices, int choicesSize, int start) {
    // Если сумма подмножества равна target, записать решение
    if (target == 0) {
        for (int i = 0; i < stateSize; i++) {
            res[resSize][i] = state[i];
        }
        resColSizes[resSize++] = stateSize;
        return;
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    // Отсечение 3: начинать обход с start, чтобы избежать повторного выбора одного и того же элемента
    for (int i = start; i < choicesSize; i++) {
        // Отсечение 1: если сумма подмножества превышает target, сразу пропустить
        if (target - choices[i] < 0) {
            continue;
        }
        // Отсечение 4: если этот элемент равен элементу слева, значит ветвь поиска повторяется, ее нужно сразу пропустить
        if (i > start && choices[i] == choices[i - 1]) {
            continue;
        }
        // Попытка: сделать выбор и обновить target и start
        state[stateSize] = choices[i];
        stateSize++;
        // Перейти к следующему выбору
        backtrack(target - choices[i], choices, choicesSize, i + 1);
        // Откат: отменить выбор и восстановить предыдущее состояние
        stateSize--;
    }
}

/* Решить задачу суммы подмножеств II */
void subsetSumII(int *nums, int numsSize, int target) {
    // Отсортировать nums
    qsort(nums, numsSize, sizeof(int), cmp);
    // Начать бэктрекинг
    backtrack(target, nums, numsSize, 0);
}
subset_sum_ii.kt
/* Алгоритм бэктрекинга: сумма подмножеств II */
fun backtrack(
    state: MutableList<Int>,
    target: Int,
    choices: IntArray,
    start: Int,
    res: MutableList<MutableList<Int>?>
) {
    // Если сумма подмножества равна target, записать решение
    if (target == 0) {
        res.add(state.toMutableList())
        return
    }
    // Обойти все варианты выбора
    // Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
    // Отсечение 3: начинать обход с start, чтобы избежать повторного выбора одного и того же элемента
    for (i in start..<choices.size) {
        // Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
        // Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
        if (target - choices[i] < 0) {
            break
        }
        // Отсечение 4: если этот элемент равен элементу слева, значит ветвь поиска повторяется, ее нужно сразу пропустить
        if (i > start && choices[i] == choices[i - 1]) {
            continue
        }
        // Попытка: сделать выбор и обновить target и start
        state.add(choices[i])
        // Перейти к следующему выбору
        backtrack(state, target - choices[i], choices, i + 1, res)
        // Откат: отменить выбор и восстановить предыдущее состояние
        state.removeAt(state.size - 1)
    }
}

/* Решить задачу суммы подмножеств II */
fun subsetSumII(nums: IntArray, target: Int): MutableList<MutableList<Int>?> {
    val state = mutableListOf<Int>() // Состояние (подмножество)
    nums.sort() // Отсортировать nums
    val start = 0 // Стартовая вершина обхода
    val res = mutableListOf<MutableList<Int>?>() // Список результатов (список подмножеств)
    backtrack(state, target, nums, start, res)
    return res
}
subset_sum_ii.rb
### Алгоритм бэктрекинга: сумма подмножеств II ###
def backtrack(state, target, choices, start, res)
  # Если сумма подмножества равна target, записать решение
  if target.zero?
    res << state.dup
    return
  end

  # Обойти все варианты выбора
  # Отсечение 2: начинать обход с start, чтобы избежать генерации повторяющихся подмножеств
  # Отсечение 3: начинать обход с start, чтобы избежать повторного выбора одного и того же элемента
  for i in start...choices.length
    # Отсечение 1: если сумма подмножества превышает target, немедленно завершить цикл
    # Это связано с тем, что массив уже отсортирован, следующие элементы больше, и сумма подмножества точно превысит target
    break if target - choices[i] < 0
    # Отсечение 4: если этот элемент равен элементу слева, значит ветвь поиска повторяется, ее нужно сразу пропустить
    next if i > start && choices[i] == choices[i - 1]
    # Попытка: сделать выбор и обновить target и start
    state << choices[i]
    # Перейти к следующему выбору
    backtrack(state, target - choices[i], choices, i + 1, res)
    # Откат: отменить выбор и восстановить предыдущее состояние
    state.pop
  end
end

### Решить задачу суммы подмножеств II ###
def subset_sum_ii(nums, target)
  state = [] # Состояние (подмножество)
  nums.sort! # Отсортировать nums
  start = 0 # Стартовая вершина обхода
  res = [] # Список результатов (список подмножеств)
  backtrack(state, target, nums, start, res)
  res
end
Визуализация кода

На рисунке 13-14 показан процесс backtracking для массива \([4, 4, 5]\) и целевого значения \(9\) . В нем используются четыре вида обрезки. Попробуйте сопоставить рисунок с комментариями в коде, чтобы понять полный процесс поиска и то, как работает каждый тип обрезки.

Процесс backtracking для задачи о сумме подмножеств II

Рисунок 13-14   Процесс backtracking для задачи о сумме подмножеств II

Оставляйте свои идеи, вопросы и предложения в комментариях