40. Combination Sum II
leetcode medium
Task
Дана коллекция кандидатов (candidates) и целевое число (target). Найдите все уникальные комбинации в candidates, где числа кандидатов в сумме дают target.
Каждое число в candidates может быть использовано только один раз в комбинации.
Примечание: Набор решений не должен содержать повторяющихся комбинаций.
Пример:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
C# solution
matched/originalpublic class Solution {
List<IList<int>> Results = new List<IList<int>>();
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
Dictionary<int, int> counter = new Dictionary<int, int>();
foreach (int candidate in candidates) {
if (counter.ContainsKey(candidate))
counter[candidate] += 1;
else
counter[candidate] = 1;
}
List<int[]> counterList = new List<int[]>();
foreach (KeyValuePair<int, int> entry in counter) {
counterList.Add(new int[] { entry.Key, entry.Value });
}
Backtrack(new List<int>(), target, 0, counterList);
return Results;
}
private void Backtrack(List<int> comb, int remain, int curr,
List<int[]> counter) {
if (remain == 0) {
Results.Add(new List<int>(comb));
return;
}
if (remain < 0) {
return;
}
for (int nextCurr = curr; nextCurr < counter.Count; ++nextCurr) {
int[] entry = counter[nextCurr];
int candidate = entry[0], freq = entry[1];
if (freq <= 0)
continue;
comb.Add(candidate);
counter[nextCurr] = new int[] { candidate, freq - 1 };
Backtrack(comb, remain - candidate, nextCurr, counter);
counter[nextCurr] = new int[] { candidate, freq };
comb.RemoveAt(comb.Count - 1);
}
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
List<vector<int>> Results = new List<vector<int>>();
public IList<vector<int>> CombinationSum2(vector<int>& candidates, int target) {
unordered_map<int, int> counter = new unordered_map<int, int>();
foreach (int candidate in candidates) {
if (counter.count(candidate))
counter[candidate] += 1;
else
counter[candidate] = 1;
}
List<int[]> counterList = new List<int[]>();
foreach (KeyValuePair<int, int> entry in counter) {
counterList.push_back(new int[] { entry.Key, entry.Value });
}
Backtrack(new List<int>(), target, 0, counterList);
return Results;
}
private void Backtrack(List<int> comb, int remain, int curr,
List<int[]> counter) {
if (remain == 0) {
Results.push_back(new List<int>(comb));
return;
}
if (remain < 0) {
return;
}
for (int nextCurr = curr; nextCurr < counter.size(); ++nextCurr) {
vector<int>& entry = counter[nextCurr];
int candidate = entry[0], freq = entry[1];
if (freq <= 0)
continue;
comb.push_back(candidate);
counter[nextCurr] = new int[] { candidate, freq - 1 };
Backtrack(comb, remain - candidate, nextCurr, counter);
counter[nextCurr] = new int[] { candidate, freq };
comb.RemoveAt(comb.size() - 1);
}
}
}Java solution
matched/originalclass Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
LinkedList<Integer> comb = new LinkedList<>();
HashMap<Integer, Integer> counter = new HashMap<>();
for (int candidate : candidates) {
counter.put(candidate, counter.getOrDefault(candidate, 0) + 1);
}
List<int[]> counterList = new ArrayList<>();
counter.forEach((key, value) -> {
counterList.add(new int[] { key, value });
});
backtrack(comb, target, 0, counterList, results);
return results;
}
private void backtrack(
LinkedList<Integer> comb,
int remain,
int curr,
List<int[]> counter,
List<List<Integer>> results
) {
if (remain <= 0) {
if (remain == 0) {
results.add(new ArrayList<Integer>(comb));
}
return;
}
for (int nextCurr = curr; nextCurr < counter.size(); ++nextCurr) {
int[] entry = counter.get(nextCurr);
Integer candidate = entry[0], freq = entry[1];
if (freq <= 0) continue;
comb.addLast(candidate);
counter.set(nextCurr, new int[] { candidate, freq - 1 });
backtrack(comb, remain - candidate, nextCurr, counter, results);
counter.set(nextCurr, new int[] { candidate, freq });
comb.removeLast();
}
}
}Python solution
matched/originalclass Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(comb, remain, curr, counter, results):
if remain == 0:
results.append(list(comb))
return
elif remain < 0:
return
for next_curr in range(curr, len(counter)):
candidate, freq = counter[next_curr]
if freq <= 0:
continue
comb.append(candidate)
counter[next_curr] = (candidate, freq - 1)
backtrack(comb, remain - candidate, next_curr, counter, results)
counter[next_curr] = (candidate, freq)
comb.pop()
results = []
counter = Counter(candidates)
counter = [(c, counter[c]) for c in counter]
backtrack(
comb=[], remain=target, curr=0, counter=counter, results=results
)
return resultsGo solution
matched/originalfunc combinationSum2(candidates []int, target int) [][]int {
results := [][]int{}
comb := []int{}
counter := map[int]int{}
for _, candidate := range candidates {
counter[candidate]++
}
counterKeys := make([]int, 0, len(counter))
for k := range counter {
counterKeys = append(counterKeys, k)
}
sort.Ints(counterKeys)
var backtrack func(int, int)
backtrack = func(start int, remain int) {
if remain == 0 {
c := make([]int, len(comb))
copy(c, comb)
results = append(results, c)
return
}
if remain < 0 {
return
}
for i := start; i < len(counterKeys); i++ {
candidate := counterKeys[i]
if counter[candidate] > 0 {
comb = append(comb, candidate)
counter[candidate]--
backtrack(i, remain-candidate)
comb = comb[:len(comb)-1]
counter[candidate]++
}
}
}
backtrack(0, target)
return results
}Explanation
Algorithm
1️⃣
Во-первых, мы создаём таблицу счётчиков из предоставленного списка чисел. Затем мы используем эту таблицу счётчиков в процессе обратного поиска, который мы определяем как функцию
backtrack(comb, remain, curr, candidate_groups, results)
. Для сохранения состояния на каждом этапе обратного поиска мы используем несколько параметров в функции:
comb
: комбинация, которую мы построили на данный момент.
remain
: оставшаяся сумма, которую нам нужно заполнить, чтобы достичь целевой суммы.
curr
: курсор, который указывает на текущую группу чисел, используемую из таблицы счётчиков.
counter
: текущая таблица счётчиков.
results
: окончательные комбинации, которые достигают целевой суммы.
2️⃣
При каждом вызове функции обратного поиска мы сначала проверяем, достигли ли мы целевой суммы (то есть
sum(comb) = target)
, и нужно ли прекратить исследование, потому что сумма текущей комбинации превышает желаемую целевую сумму.
3️⃣
Если осталась сумма для заполнения, мы затем перебираем текущую таблицу счётчиков, чтобы выбрать следующего кандидата. После выбора кандидата мы продолжаем исследование, вызывая функцию
backtrack()
с обновлёнными состояниями. Более важно, что в конце каждого исследования нам нужно вернуть состояние, которое мы обновили ранее, чтобы начать с чистого листа для следующего исследования. Именно из-за этой операции обратного поиска алгоритм получил своё название.
😎