1 Тема від Teg Miles

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 530
    • Репутація: 106

Тема: Додавання map до tuple в stack

Намагаюся вирішити завдання:

40. Combination Sum II
Medium
Topics
Companies

Given a collection of candidate numbers (candidates) and a target number
(target), find all unique combinations in candidates where the candidate
numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.



Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]



Constraints:

    1 <= candidates.length <= 100
    1 <= candidates[i] <= 50
    1 <= target <= 30

Але ітеративним методом. Ось так:

class Solution {
public:
    auto combinationSum2(const std::vector<int>& candidates, const int target)
        -> std::vector<std::vector<int>>
    {
        std::vector<std::vector<int>> answer;
        auto candidates_size = static_cast<int>(std::ranges::size(candidates));
        std::stack<std::tuple<std::unordered_map<int, int>, std::vector<int>,
                              int, int>>
            combs;
        std::vector<int> helper;
        std::unordered_map<int, int> helper_map;

        combs.emplace(helper_map, helper, target, 0);

        std::unordered_map<int, int> freq;
        for (const auto& item : candidates) {
            ++freq[item];
        }
        while (!combs.empty()) {
            auto [cur_freq, current, remaining, index]
                = std::move(combs.top());
            combs.pop();
            if (remaining == 0) {
                answer.emplace_back(current);
                continue;
            }

            for (int i = index; i < candidates_size; ++i) {
                ++cur_freq[candidates[i]];
                if (candidates[i] > remaining
                    || cur_freq[candidates[i]] > freq[candidates[i]]) {
                    continue;
                }

                current.emplace_back(candidates[i]);
                std::vector<int> next_combo(current);
                combs.emplace(next_combo, remaining - candidates[i], i);
            }
        }

        return answer;
    }
};

Проте отримую ось таку помилку при додаванні map до т'юплу стека:

In file included from /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/14.2.1/../../../../include/c++/14.2.1/complex:45:
In file included from /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/14.2.1/../../../../include/c++/14.2.1/sstream:40:
In file included from /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/14.2.1/../../../../include/c++/14.2.1/istream:40:
In file included from /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/14.2.1/../../../../include/c++/14.2.1/ios:44:
In file included from /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/14.2.1/../../../../include/c++/14.2.1/bits/ios_base.h:41:
In file included from /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/14.2.1/../../../../include/c++/14.2.1/bits/locale_classes.h:40:
In file included from /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/14.2.1/../../../../include/c++/14.2.1/string:54:
In file included from /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/14.2.1/../../../../include/c++/14.2.1/bits/basic_string.h:39:
In file included from /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/14.2.1/../../../../include/c++/14.2.1/ext/alloc_traits.h:34:
/usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/14.2.1/../../../../include/c++/14.2.1/bits/alloc_traits.h:577:4: error: no matching function for call to 'construct_at'
  577 |           std::construct_at(__p, std::forward<_Args>(__args)...);
      |           ^~~~~~~~~~~~~~~~~
/usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/14.2.1/../../../../include/c++/14.2.1/bits/deque.tcc:170:21: note: in instantiation of function template specialization 'std::allocator_traits<std::allocator<std::tuple<std::unordered_map<int, int>, std::vector<int>, int, int>>>::construct<std::tuple<std::unordered_map<int, int>, std::vector<int>, int, int>, std::vector<int> &, int, int &>' requested here
  170 |             _Alloc_traits::construct(this->_M_impl,
      |                            ^
/usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/14.2.1/../../../../include/c++/14.2.1/bits/stl_stack.h:270:13: note: in instantiation of function template specialization 'std::deque<std::tuple<std::unordered_map<int, int>, std::vector<int>, int, int>>::emplace_back<std::vector<int> &, int, int &>' requested here
  270 |         { return c.emplace_back(std::forward<_Args>(__args)...); }
      |                    ^
/usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/14.2.1/../../../../include/c++/14.2.1/bits/stl_construct.h:94:5: note: candidate template ignored: substitution failure [with _Tp = std::tuple<std::unordered_map<int, int>, std::vector<int>, int, int>, _Args = <std::vector<int> &, int, int &>]: no matching constructor for initialization of 'std::tuple<std::unordered_map<int, int>, std::vector<int>, int, int>'
   94 |     construct_at(_Tp* __location, _Args&&... __args)
      |     ^
   95 |     noexcept(noexcept(::new((void*)0) _Tp(std::declval<_Args>()...)))
   96 |     -> decltype(::new((void*)0) _Tp(std::declval<_Args>()...))
      |                                 ~~~
1 error generated.

Розумію, що намагаюся впихнути невпихуєме, але ніяк не збагну причини невпихуємості:)
Наче мало б працювати.

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 688
    • Репутація: 13390

Re: Додавання map до tuple в stack

Teg Miles написав:
std::stack<std::tuple<std::unordered_map<int, int>, std::vector<int>,
                              int, int>>
            combs;

combs - стек з тьюплів з 4 елементів (хеш, вектор, 2 цілих)

Teg Miles написав:
combs.emplace(next_combo, remaining - candidates[i], i);

Тут ніби 3 елементи (якщо я ще лічити не розучився).

Якщо чесно, то я не знаю, як тут "по науці", але мені очевидно, що якщо відсортувати масив за спаданням, то комбінації, що перевищують суму, будуть відсіюватися значно швидше. Також було б непогано порахувати суми "хвостів" (просто накопичувальні суми) і якщо хвіст менший за залишок, припиняти пошук. Але це дрібні оптимізації; загальна ж кількість комбінацій - O(2n), а тут 1 <= candidates.length <= 100.

Подякували: Teg Miles1

koala вебсайт

3 Відповідь від Teg Miles

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 530
    • Репутація: 106

Re: Додавання map до tuple в stack

koala написав:
Teg Miles написав:
std::stack<std::tuple<std::unordered_map<int, int>, std::vector<int>,
                              int, int>>
            combs;

combs - стек з тьюплів з 4 елементів (хеш, вектор, 2 цілих)

Teg Miles написав:
combs.emplace(next_combo, remaining - candidates[i], i);

Тут ніби 3 елементи (якщо я ще лічити не розучився).

Якщо чесно, то я не знаю, як тут "по науці", але мені очевидно, що якщо відсортувати масив за спаданням, то комбінації, що перевищують суму, будуть відсіюватися значно швидше. Також було б непогано порахувати суми "хвостів" (просто накопичувальні суми) і якщо хвіст менший за залишок, припиняти пошук. Але це дрібні оптимізації; загальна ж кількість комбінацій - O(2n), а тут 1 <= candidates.length <= 100.

Про сортування не подумав, треба буде спробувати.

4 Відповідь від Teg Miles

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 530
    • Репутація: 106

Re: Додавання map до tuple в stack

Ось таке працює, але потрібна оптимізація:

class Solution {
public:
    auto combinationSum2(std::vector<int>& candidates, const int target)
        -> std::vector<std::vector<int>>
    {
        std::vector<std::vector<int>> answer;
        auto candidates_size = static_cast<int>(std::ranges::size(candidates));
        std::stack<std::tuple<std::vector<int>, std::vector<int>, int, int>>
            combs;
        constexpr int num_limit = 51;
        std::vector<int> freq(num_limit, 0);
        for (const auto& item : candidates) {
            ++freq[item];
        }
        std::vector<int> helper;
        std::vector<int> helper_map(num_limit, 0);

        combs.emplace(helper_map, helper, target, 0);
        std::ranges::sort(candidates, std::ranges::greater {});
        while (!combs.empty()) {
            auto [cur_freq, current, remaining, index]
                = std::move(combs.top());
            combs.pop();
            if (remaining == 0) {
                auto is_exist = std::ranges::count(answer, current);
                if (is_exist == 0) {
                    answer.emplace_back(current);
                }

                continue;
            }

            for (int i = index; i < candidates_size; ++i) {
                ++cur_freq[candidates[i]];
                if (candidates[i] > remaining
                    || cur_freq[candidates[i]] > freq[candidates[i]]) {
                    continue;
                }
                std::vector<int> next_combo(current);
                next_combo.emplace_back(candidates[i]);
                std::vector<int> next_freq(cur_freq);
                combs.emplace(next_freq, next_combo, remaining - candidates[i],
                              i);
            }
        }

        return answer;
    }
};

Бо на таких випадках дуже повільно виходить:
candidates =
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
target =
27

5 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 688
    • Репутація: 13390

Re: Додавання map до tuple в stack

▼Мій поганий (судячи зі статистики на літкоді) розв'язок
#include <cstdint>
#include  <ranges>

class Solution {
    struct DataElem {
        uint16_t number;
        uint16_t count;
        uint16_t tail;
    };
    struct SolutionCandidate {
        std::vector<uint16_t> counts;
        uint16_t remains;
    };
public:
    std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates, int target) {
        std::vector<int> sorted { candidates };
        std::sort(sorted.begin(), sorted.end());
        std::vector<DataElem> data;
        for(auto c: std::ranges::views::reverse(sorted)) {
            if(data.empty() || data.back().number != c)
                data.emplace_back(DataElem{static_cast<uint16_t>(c), 1, 0});
            else
                ++data.back().count;
        }
        uint16_t tail = 0;
        for(auto& elem: std::views::reverse(data)) {
            tail += elem.number * elem.count;
            elem.tail = tail;
        }
        std::stack<SolutionCandidate> stack;
        stack.push( SolutionCandidate{{}, static_cast<uint16_t>(target)} );
        std::vector<std::vector<int>> results;
        while(!stack.empty()) {
            auto candidate = stack.top();
            stack.pop();
            const auto &num = data[candidate.counts.size()];
            if(candidate.remains==num.tail) { //all the rest is in the solution
                std::vector<int> result;
                for(size_t i=0; i<candidate.counts.size(); ++i) 
                    for(size_t j=0; j<candidate.counts[i]; ++j)
                        result.emplace_back(data[i].number);
                for(size_t i=candidate.counts.size(); i<data.size(); ++i)
                    for(size_t j=0; j<data[i].count; ++j)
                        result.emplace_back(data[i].number);
                results.emplace_back(result);
                continue;
            }
            if(candidate.counts.size()==data.size()-1) { //last element
                uint16_t count = candidate.remains/num.number;
                if(count <= num.count && count*num.number==candidate.remains) {
                    std::vector<int> result;
                    for(size_t i=0; i<candidate.counts.size(); ++i) 
                        for(size_t j=0; j<candidate.counts[i]; ++j)
                            result.emplace_back(data[i].number);
                    for(size_t j=0; j<count; ++j)
                        result.emplace_back(num.number);
                    results.emplace_back(result);                    
                }
                continue;
            }
            
            for(uint16_t i = 0; i <= num.count; ++i) {
                if(num.number * i > candidate.remains)
                    break;
                if(num.number * i == candidate.remains) {
                    std::vector<int> result;
                    for(size_t k=0; k<candidate.counts.size(); ++k) 
                        for(size_t j=0; j<candidate.counts[k]; ++j)
                            result.emplace_back(data[k].number);
                    for(size_t j=0; j<i; ++j)
                        result.emplace_back(num.number);
                    results.emplace_back(result);
                    break;
                }
                SolutionCandidate new_candidate {candidate};
                new_candidate.counts.emplace_back(i);
                new_candidate.remains -= num.number * i;
                stack.push(new_candidate);
            }
        }
        return results;
    }
};

Значить, є хороший алгоритм, треба читати...

koala вебсайт

6 Відповідь від Teg Miles

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 530
    • Репутація: 106

Re: Додавання map до tuple в stack

Ось робоча версія з обрізанням дублікатів:

class Solution {
public:
    auto combinationSum2(std::vector<int>& candidates, const int target)
        -> std::vector<std::vector<int>>
    {
        std::vector<std::vector<int>> answer;
        auto total = std::accumulate(candidates.begin(), candidates.end(), 0);

        if (total < target) {
            return answer;
        }
        if (total == target) {
            answer.emplace_back(candidates);
            return answer;
        }
        auto candidates_size = static_cast<int>(std::ranges::size(candidates));
        std::stack<std::tuple<std::vector<int>, std::vector<int>, int, int>>
            combs;
        constexpr int num_limit = 51;
        std::vector<int> freq(num_limit, 0);
        for (const auto& item : candidates) {
            ++freq[item];
        }
        std::vector<int> helper;
        std::vector<int> helper_map(num_limit, 0);

        combs.emplace(helper_map, helper, target, 0);
        std::ranges::sort(candidates, std::ranges::greater {});

        while (!combs.empty()) {
            auto [cur_freq, current, remaining, index]
                = std::move(combs.top());
            combs.pop();
            if (remaining == 0) {
                answer.emplace_back(current);
                continue;
            }

            for (int i = index; i < candidates_size; ++i) {
                ++cur_freq[candidates[i]];
                if (candidates[i] > remaining
                    || cur_freq[candidates[i]] > freq[candidates[i]]
                    || (i != index && candidates[i] == candidates[i - 1])) {
                    continue;
                }
                std::vector<int> next_combo(current);
                next_combo.emplace_back(candidates[i]);
                std::vector<int> next_freq(cur_freq);
                combs.emplace(next_freq, next_combo, remaining - candidates[i],
                              i);
            }
        }

        return answer;
    }
};

Ось ця умова допомогла позбутися дублікатів на льоту:

i != index && candidates[i] == candidates[i - 1]

7 Відповідь від Teg Miles

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 530
    • Репутація: 106

Re: Додавання map до tuple в stack

koala написав:
▼Мій поганий (судячи зі статистики на літкоді) розв'язок
#include <cstdint>
#include  <ranges>

class Solution {
    struct DataElem {
        uint16_t number;
        uint16_t count;
        uint16_t tail;
    };
    struct SolutionCandidate {
        std::vector<uint16_t> counts;
        uint16_t remains;
    };
public:
    std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates, int target) {
        std::vector<int> sorted { candidates };
        std::sort(sorted.begin(), sorted.end());
        std::vector<DataElem> data;
        for(auto c: std::ranges::views::reverse(sorted)) {
            if(data.empty() || data.back().number != c)
                data.emplace_back(DataElem{static_cast<uint16_t>(c), 1, 0});
            else
                ++data.back().count;
        }
        uint16_t tail = 0;
        for(auto& elem: std::views::reverse(data)) {
            tail += elem.number * elem.count;
            elem.tail = tail;
        }
        std::stack<SolutionCandidate> stack;
        stack.push( SolutionCandidate{{}, static_cast<uint16_t>(target)} );
        std::vector<std::vector<int>> results;
        while(!stack.empty()) {
            auto candidate = stack.top();
            stack.pop();
            const auto &num = data[candidate.counts.size()];
            if(candidate.remains==num.tail) { //all the rest is in the solution
                std::vector<int> result;
                for(size_t i=0; i<candidate.counts.size(); ++i) 
                    for(size_t j=0; j<candidate.counts[i]; ++j)
                        result.emplace_back(data[i].number);
                for(size_t i=candidate.counts.size(); i<data.size(); ++i)
                    for(size_t j=0; j<data[i].count; ++j)
                        result.emplace_back(data[i].number);
                results.emplace_back(result);
                continue;
            }
            if(candidate.counts.size()==data.size()-1) { //last element
                uint16_t count = candidate.remains/num.number;
                if(count <= num.count && count*num.number==candidate.remains) {
                    std::vector<int> result;
                    for(size_t i=0; i<candidate.counts.size(); ++i) 
                        for(size_t j=0; j<candidate.counts[i]; ++j)
                            result.emplace_back(data[i].number);
                    for(size_t j=0; j<count; ++j)
                        result.emplace_back(num.number);
                    results.emplace_back(result);                    
                }
                continue;
            }
            
            for(uint16_t i = 0; i <= num.count; ++i) {
                if(num.number * i > candidate.remains)
                    break;
                if(num.number * i == candidate.remains) {
                    std::vector<int> result;
                    for(size_t k=0; k<candidate.counts.size(); ++k) 
                        for(size_t j=0; j<candidate.counts[k]; ++j)
                            result.emplace_back(data[k].number);
                    for(size_t j=0; j<i; ++j)
                        result.emplace_back(num.number);
                    results.emplace_back(result);
                    break;
                }
                SolutionCandidate new_candidate {candidate};
                new_candidate.counts.emplace_back(i);
                new_candidate.remains -= num.number * i;
                stack.push(new_candidate);
            }
        }
        return results;
    }
};

Значить, є хороший алгоритм, треба читати...

На Літкоді все заточено під змагання, а ітерація дуже рідко обганяє рекурсію на коротких відстанях.
У мене теж вийшло приблизно 10% Runtime i 5% Memory порівняно з рекурсією.