algorithm

LeetCode - Combination Sum II

Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.

先对C里的数字计数，然后递归处理，每个数字出现[0, count[num]]次。
自己写了个AVL树作为map计数。然后没有维护unique-number的列表，把AVL树先转成线索二叉树，然后遍历，结束后再转回普通树结构。不要问我为啥这么写，闲的。

AVL Tree实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
const size_t AVLTREE_MAX_HEIGHT = 62;

struct AVLTreeNode {
    AVLTreeNode* left;
    AVLTreeNode* right;
    int height;
    size_t key;
    int value;
    AVLTreeNode(size_t k=0, int v=0) : left(nullptr), right(nullptr), height(1), key(k), value(v) {}
};

int avl_height(AVLTreeNode* root) {
    return root?root->height:0;
}

int avl_height_update(AVLTreeNode* root) {
    // assert(root!=NULL);
    return (root->height = std::max(avl_height(root->left), avl_height(root->right)) + 1);
}

int avl_balance_factor(AVLTreeNode* root) {
    // assert(root!=NULL);
    return avl_height(root->left) - avl_height(root->right);
}

AVLTreeNode* avl_rotate_left(AVLTreeNode* root) {
    // assert(root!=nullptr);
    AVLTreeNode* right = root->right;
    // assert(right!=nullptr);
    root->right= right->left;
    right->left = root;
    avl_height_update(root);
    avl_height_update(right);
    return right;
}

AVLTreeNode* avl_rotate_right(AVLTreeNode* root) {
    // assert(root!=nullptr);
    AVLTreeNode* left = root->left;
    // assert(right!=nullptr);
    root->left = left->right;
    left->right = root;
    avl_height_update(root);
    avl_height_update(left);
    return left;
}

// true:    insert;
// false:   update;
bool avl_insert(AVLTreeNode*& root, size_t key, int value) {
    AVLTreeNode* path[AVLTREE_MAX_HEIGHT] = {nullptr};
    int top_pos = 1;
    AVLTreeNode* curr = root;
    while(curr!=NULL) {
        path[top_pos++] = curr;
        if(curr->key>key) {
            curr = curr->left;
        } else if(curr->key<key) {
            curr = curr->right;
        } else {
            curr->value = value;
            return false;
        }
    }

    curr = new AVLTreeNode(key, value);
    AVLTreeNode* parent = path[--top_pos];
    if(parent==nullptr) root = curr;
    else if(parent->key<key) parent->right = curr;
    else parent->left = curr;

    while(parent!=nullptr) {
        int parent_balance_factor = avl_balance_factor(parent);
        int curr_balance_factor = avl_balance_factor(curr);
        if(parent_balance_factor==2) {
            if(curr_balance_factor==-1) {
                curr = avl_rotate_left(curr);
                parent->left = curr;
            }

            AVLTreeNode** p_parent_parent = nullptr;
            if(path[top_pos-1]==nullptr)
                p_parent_parent = &root;
            else if(path[top_pos-1]->left == parent)
                p_parent_parent = &path[top_pos-1]->left;
            else
                p_parent_parent = &path[top_pos-1]->right;

            parent = avl_rotate_right(parent);
            *p_parent_parent = parent;
            break;
        } else if(parent_balance_factor==-2) {
            if(curr_balance_factor==1) {
                curr = avl_rotate_right(curr);
                parent->right = curr;
            }

            AVLTreeNode** p_parent_parent = nullptr;
            if(path[top_pos-1]==nullptr)
                p_parent_parent = &root;
            else if(path[top_pos-1]->left == parent)
                p_parent_parent = &path[top_pos-1]->left;
            else
                p_parent_parent = &path[top_pos-1]->right;

            parent = avl_rotate_left(parent);
            *p_parent_parent = parent;
            break;
        } else if(parent_balance_factor==0) {
            break;
        }
        avl_height_update(parent);
        curr = parent;
        parent = path[--top_pos];
    }
    return true;
}

bool avl_search(AVLTreeNode* const root, size_t key, int* value) {
    AVLTreeNode* temp = root;
    while(temp) {
        if(temp->key==key) {
            if(value) *value = temp->value;
            return true;
        }
        if(temp->key < key) {
            temp = temp->right;
        } else {
            temp = temp->left;
        }
    }
    return false;
}

bool avl_delete(AVLTreeNode*& root, size_t key, int* value) {
    AVLTreeNode* path[AVLTREE_MAX_HEIGHT] = {nullptr};
    int top_pos = 1;
    AVLTreeNode* curr = root;
    AVLTreeNode* remove = nullptr;
    while(curr!=NULL) {
        if(curr->key==key)
            break;
        path[top_pos++] = curr;
        if(curr->key>key)
            curr = curr->left;
        else
            curr =curr->right;
    }
    if(curr==nullptr)
        return false;

    remove = curr;
    if(curr->left!=nullptr && curr->right!=nullptr)
    {
        remove = curr->left;
        path[top_pos++] = curr;
        while(remove->right) {
            path[top_pos++] = remove;
            remove = remove->right;
        }
    }

    AVLTreeNode* parent = path[--top_pos];
    if(parent==nullptr) {
        // assert(remove==curr);
        root = remove->left ? remove->left : remove->right;
        delete(remove);
        return true;
    }

    if(remove!=curr) {
        curr->key = remove->key;
        curr->value = remove->value;
    }
    curr = remove->left ? remove->left : remove->right;
    if(remove==parent->left)
        parent->left = curr;
    else
        parent->right = curr;

    delete(remove);

    while(parent!=nullptr) {
        parent->height = avl_height_update(parent);
        int parent_balance_factor = avl_balance_factor(parent);
        if(parent_balance_factor==2) {
            int curr_balance_factor = avl_balance_factor(parent->left);
            if(curr_balance_factor==-1)
                parent->left = avl_rotate_left(parent->left);

            AVLTreeNode** p_parent_parent = nullptr;
            if(path[top_pos-1]==nullptr)
                p_parent_parent = &root;
            else if(path[top_pos-1]->left == parent)
                p_parent_parent = &path[top_pos-1]->left;
            else
                p_parent_parent = &path[top_pos-1]->right;

            parent = avl_rotate_right(parent);
            *p_parent_parent = parent;
            break;
        } else if(parent_balance_factor==-2) {
            int curr_balance_factor = avl_balance_factor(parent->right);
            if(curr_balance_factor==1)
                parent->right = avl_rotate_right(parent->right);

            AVLTreeNode** p_parent_parent = nullptr;
            if(path[top_pos-1]==nullptr)
                p_parent_parent = &root;
            else if(path[top_pos-1]->left == parent)
                p_parent_parent = &path[top_pos-1]->left;
            else
                p_parent_parent = &path[top_pos-1]->right;

            parent = avl_rotate_left(parent);
            *p_parent_parent = parent;
            break;
        } else if(parent_balance_factor == 1 || parent_balance_factor == -1) {
            break;
        }
        avl_height_update(parent);
        parent = path[--top_pos];
    }
    return true;
}

题目实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        AVLTreeNode* head = nullptr;
        int sum = 0;
        for(auto item: num) {
            int value = 0;
            bool ret = avl_search(head, item, &value);
            avl_insert(head, item, value+1);
        }
        vector<vector<int>> result;
        vector<int> buffer;
        buffer.reserve(num.size()/2);

        // 先将二叉树转成线索二叉树，然后再转换回来。
        // trans to threaded thee;
        AVLTreeNode* curr = head;
        AVLTreeNode* thread_head = nullptr;
        while(curr) {
            if(curr->left==nullptr) {
                if(thread_head==nullptr) thread_head = curr;
                curr = curr->right;
                continue;
            }
            AVLTreeNode* left = curr->left;
            while(left->right && left->right!=curr) left = left->right;
            if(left->right == nullptr) {
                left->right = curr;
                curr = curr->left;
            } else {
                curr = curr->right;
            }
        }

        dfs(thread_head, target, buffer, result);

        // unthread
        curr = thread_head;
        while(curr) {
            if(curr->left == nullptr) {
                curr = curr->right;
                continue;
            }
            AVLTreeNode* left = curr->left;
            while(left->right && left->right!=curr) left = left->right;
            if(left->right == curr) {
                left->right = nullptr;
                curr = curr->right;
            } else {
                assert(false && "should not here");
                curr = curr->left;
            }
        }
        return result;
    }
private:
    void dfs(AVLTreeNode* head, int target, vector<int>& tpl, vector<vector<int>>& result) {
        if(head==nullptr) return;
        int num = head->key;
        int i = 0;

        AVLTreeNode* next = head->right;
        AVLTreeNode* left = next ? next->left : nullptr;
        if(left) {
            while(left->right && left->right!=next) left = left->right;
            if(left != head) {
                while(next->left) next = next->left;
            }
        }

        do{
            if(target==0) result.push_back(tpl);
            else if(target>num) dfs(next, target, tpl, result);

            ++i;
            tpl.push_back(num);
            target -= num;
        }while(i<=head->value && target >=0);
        tpl.resize(tpl.size()-i);
    }
};

int main(int argc, char** argv) {
    vector<int> nums = {4,4,2,1,4,2,2,1,3};
    int target = 6;
    Solution s;

    auto result = s.combinationSum2(nums, target);
    cout << result.size() << endl;

    for(auto& item : result) {
        cout << "size(" << item.size() << ") ";
        for(auto val : item) {
            cout << val << ", ";
        }
        cout << endl;
    }
    return 0;
}

最开始是用它解Word Break的，但是hash冲突了，我也懒得再给TreeNode补个开链实现。