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

int cmp(int a, int b) {
    return a < b;
}
class Solution {
public:
    vector<vector<int>> fourSum(vector<int> &num, int target) {
        sort(num.begin(), num.end(), cmp);
        vector<vector<int>> ans;
        ans.clear();
        if (num.size() <= 3) return ans;
        for (int i = 0; i < num.size() - 3; i++) {
            for (int j = i + 1; j < num.size() - 2; j++) {
                for (int k = j + 1; k < num.size() - 1; k++) {
                    int val = target - (num[i] + num[j] + num[k]);
                    if (val >= num[k + 1] && findTarget(k + 1, num.size() - 1, val, num)) {
                        vector<int> item;
                        item.clear();
                        item.push_back(num[i]);
                        item.push_back(num[j]);
                        item.push_back(num[k]);
                        item.push_back(val);
                        if (!checkExist(ans, item))
                            ans.push_back(item);
                    }
                }
            }
        }
        return ans;
    }

private:
    bool checkExist(vector<vector<int>> &ans, vector<int> &item) {
        for (int i = 0; i < ans.size(); i++) {
            if (item == ans[i]) return true;
        }
        return false;
    }
    bool findTarget(int left, int right, int target, vector<int> &num) {
        if (left > right) return false;
        int mid = (left + right) / 2;
        if (num[mid] == target) return true;
        else if (num[mid] > target) {
            return findTarget(left, mid - 1, target, num);
        } else {
            return findTarget(mid + 1, right, target, num);
        }
    }
};