# 40 Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.
Each number inCmay only be usedoncein the combination.
Note:
• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.
For example, given candidate set`[10, 1, 2, 7, 6, 1, 5]`and target`8`, A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
• These I thought this was a really great problem, I wrote about the details of my implementation in my other book Algorithms and Data Structures B.
struct Key
{
Key() {};
Key(const int val, const int iter, const int sum) :
val(val), iter(iter), sum(sum) {}
int val, iter, sum;
bool operator==(const Key &other) const
{
return (val == other.val
&& iter == other.iter
&& sum == other.sum);
}
};
namespace std {
template <>
struct hash<Key>
{
std::size_t operator()(const Key& k) const
{
return ((hash<int>()(k.val)
^ (hash<int>()(k.iter) << 1)) >> 1)
^ (hash<int>()(k.sum) << 1);
}
};
}
struct TreeNode2 {
TreeNode2(Key key) :
key(key) {}
TreeNode2() {};
Key key;
vector<TreeNode2 *> children;
};
class CombinationTree {
public:
explicit CombinationTree(vector<int> nums, int target) :
target(target) {
root = new TreeNode2();
sort(nums.begin(), nums.end());
elms = nums;
for (int i = 0; i < nums.size() && nums.at(i) <= target; i++) {
Key key = Key(nums.at(i), i, nums.at(i));
TreeNode2 *base_node = new TreeNode2(key);
// identifing another subpath within a prebuilt path
// but the idea is that if we put this path from the root
// the it will become part of the valid set when
// seaching all the root to leaf paths
if (dp_hash_map.find(key) != dp_hash_map.end()) {
root->children.push_back(dp_hash_map[key]);
continue; // subtree exist
}
dp_hash_map.insert(make_pair(key, base_node));
root->children.push_back(base_node);
base_node->children = build_combination_tree(base_node);
}
}
vector<vector<int>> root_leaf_paths(TreeNode2 *root, int target) {
// good idea to use static parameters here (single reference)
// just need to make sure to reset on deconstruction
vector<vector<int>> main;
vector<int> temp;
unordered_set<string> unique_paths;
string temp_str = "";
// ignore the root
for (TreeNode2 *n : root->children)
root_leaf_paths_rec(n, temp, main, target, unique_paths, temp_str);
return main;
}
static void print_level_order(TreeNode2 *root)
{
if (!root) return;
cout << "Value:Iterator:Accumulative Sum:Number Children" << endl << endl;
queue<TreeNode2*> q;
q.push(root);
q.push(nullptr);
while (!q.empty()) {
TreeNode2 *temp = q.front();
if (temp)
cout << temp->key.val << ":" <<
temp->key.iter << ":" << temp->key.sum << ":"
<< temp->children.size() << " ";
q.pop();
if (temp) {
for (TreeNode2 *t : temp->children)
if (t) q.push(t);
}
else {
if (!q.empty() && q.front()) {
q.push(nullptr);
cout << endl;
}
}
}
}
TreeNode2 *root;
private:
vector<int> elms;
unordered_map<Key, TreeNode2*> dp_hash_map;
int target;
vector<TreeNode2*> build_combination_tree(TreeNode2* cur_node)
{
// current node attributes
int cur_iter = cur_node->key.iter;
int cur_sum = cur_node->key.sum;
int cur_val = cur_node->key.val;
vector<TreeNode2*> next_children;
for (int i = cur_iter + 1; i < elms.size() && cur_sum < target; i++) {
// if the sub tree exists, then do not bother creating
// the same subtree for it
Key key = Key(elms.at(i), i, cur_sum + elms.at(i));
if (dp_hash_map.find(key) != dp_hash_map.end()) {
// point to the already developed subtree, and continue.
next_children.push_back(dp_hash_map[key]);
}
else {
TreeNode2* next_node = new TreeNode2(key);
dp_hash_map.insert(make_pair(key, next_node));
next_children.push_back(next_node);
next_node->children = build_combination_tree(next_node);
}
}
return next_children;
}
/*
* Performs traversal of combination tree
* to collect valid summations
*/
void root_leaf_paths_rec(TreeNode2 *root,
vector<int> &temp,
vector<vector<int>> &main, const int target,
unordered_set<string> &unique_paths,
string &temp_str) {
if (root) {
temp_str += to_string(root->key.val) + " ";
temp.push_back(root->key.val);
if (root->children.empty() && root->key.sum == target
&& unique_paths.find(temp_str) == unique_paths.end()) {
main.push_back(temp);
unique_paths.insert(temp_str);
temp.pop_back();
pop_back_last_num(temp_str);
return;
}
for (TreeNode2 *t : root->children) {
if (t) root_leaf_paths_rec(t, temp, main, target, unique_paths, temp_str);
}
}
temp.pop_back();
pop_back_last_num(temp_str);
}
void pop_back_last_num(string &complete_str)
{
int iter = complete_str.length() - 2; // ignore first space
while (iter >= 0 && complete_str.at(iter) != ' ')
iter--;
complete_str = complete_str.substr(0, max(0,iter + 1));
}
};
Some Testing:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
{
CombinationTree t = CombinationTree(candidates, target);
//t.print_level_order(t.root);
return t.root_leaf_paths(t.root, target);
}
int main(int argc, char **argv)
{
vector<int> test1 = { 10, 1, 2, 7, 6, 1, 5 };
print2d(combinationSum2(test1, 8));
vector<int> test2 = { 1,1,2 };
print2d(combinationSum2(test2, 3));
vector<int> test3 = { 1,-2,3,4,-5,6,7,-8,90,-23,45,67,89 };
print2d(combinationSum2(test3, 6));
}