// https://leetcode.com/problems/combination-sum-ii/
// gcc -std=c++11 -g -O0 combsum.cpp -fsanitize=address -o combsum -lstdc++
// FIXME!!! add description

#include <algorithm>
#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>

class Solution {
public:
  std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates,
                                                int target) {
    using Result = std::vector<std::unordered_set<int>>;
    std::vector<Result> cache(target);

    // initial data
    for (int j = 0; j < candidates.size(); j++) {
      if (candidates[j] <= target) {
        cache[candidates[j] - 1].push_back(std::unordered_set<int>{j});
      }
    }
    // fill cache
    for (int i = 0; i < target; i++) {
      if (cache[i].empty()) continue;

      for (int k = 0; k < candidates.size(); ++k) {
        if (candidates[k] + i < target) {
          for (auto data : cache[i]) {
            if (data.find(k) != data.end()) continue;
            data.insert(k);
            cache[candidates[k] + i].push_back(data);
          }
        }
      }
    }
    // remove dublicates
    std::set<std::vector<int>> tmp;
    for (auto item : cache[target - 1]) {
      std::vector<int> line;
      for (auto idx : item) {
        line.push_back(candidates[idx]);
      }
      std::sort(line.begin(), line.end());
      tmp.insert(line);
    }

    std::vector<std::vector<int>> res(tmp.begin(), tmp.end());
    return res;
  }
};

int main() {
  std::vector<int> candidates = {10, 1, 2, 7, 6, 1, 5, 8};
  int target = 8;
  auto res = Solution().combinationSum2(candidates, target);
  std::cout << "Solution: " << std::endl;

  for (auto iter = res.begin(); iter != res.end(); ++iter) {
    std::cout << "[ ";
    std::for_each(iter->begin(), iter->end(),
                  [](int n) { std::cout << n << " "; });
    std::cout << "]" << std::endl;
  }

  return 0;
}
