40. Combination Sum II
Дана коллекция кандидатов (candidates) и целевое number (target). find все уникальные комбинации в candidates, где числа кандидатов в сумме дают target.
Каждое number в candidates может быть использовано только один раз в комбинации.
Примечание: Набор решений не должен содержать повторяющихся комбинаций.
Ví dụ:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
C# lời giải
đã khớp/gốcpublic 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++ lời giải
bản nháp tự động, xem lại trước khi gửi#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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcfunc 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
}Algorithm
1️⃣
Во-первых, мы создаём таблицу счётчиков из предоставленного списка чисел. Затем мы используем эту таблицу счётчиков в процессе обратного поиска, который мы определяем как функцию
backtrack(comb, remain, curr, candidate_groups, results)
. Для сохранения состояния на каждом этапе обратного поиска мы используем несколько параметров в функции:
comb
: комбинация, которую мы построили на данный момент.
remain
: оставшаяся сумма, которую нам нужно заполнить, чтобы достичь целевой суммы.
curr
: курсор, который указывает на текущую группу чисел, используемую из таблицы счётчиков.
counter
: текущая таблица счётчиков.
results
: окончательные комбинации, которые достигают целевой суммы.
2️⃣
При каждом вызове функции обратного поиска мы сначала проверяем, достигли ли мы целевой суммы (то есть
sum(comb) = target)
, и нужно ли прекратить исследование, потому что сумма текущей комбинации превышает желаемую целевую сумму.
3️⃣
Если осталась сумма для заполнения, мы затем перебираем текущую таблицу счётчиков, чтобы выбрать следующего кандидата. После выбора кандидата мы продолжаем исследование, вызывая функцию
backtrack()
с обновлёнными состояниями. Более важно, что в конце каждого исследования нам нужно вернуть состояние, которое мы обновили ранее, чтобы начать с чистого листа для следующего исследования. Именно из-за этой операции обратного поиска Thuật toán получил своё название.
😎
Vacancies for this task
việc làm đang hoạt động with overlapping task tags are đã hiển thị.