40. Combination Sum II

public 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);
        }
    }
}

#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);
        }
    }
}

class 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();
        }
    }
}

class 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 results

func 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()

с обновлёнными состояниями. Более важно, что в конце каждого исследования нам нужно вернуть состояние, которое мы обновили ранее, чтобы начать с чистого листа для следующего исследования. Именно из-за этой операции обратного поиска 算法 получил своё название.

😎