# C++ DFS search with path cut 136ms

• ``````class Solution {
public:
void divide(vector<int> &a, vector<int> &a0, vector<int> &a1, int bitPos) {
if (bitPos > 31 || bitPos < 0) return;
for (int i = 0; i < a.size(); i++) {
if ((a[i] & (1<<bitPos)) == 0) {
a0.push_back(a[i]);
} else {
a1.push_back(a[i]);
}
}
}
//a0 and a1 are divided by bitPos, you want to see if there is a possibility
int dfs(vector<int> &a0, vector<int> &a1, int bitPos, int cur_val, int cur_max) {
if (bitPos == 0) {
if (a0.size() && a1.size()) {
cur_val |= (1<<bitPos);
cur_max = max(cur_val, cur_max);
}
return cur_max;
}

if (!a0.size() || !a1.size()) {
vector<int> &c = a0.size() ?a0 :a1;
vector<int> c0, c1;
divide(c, c0, c1, bitPos-1);
return dfs(c0, c1, bitPos-1, cur_val, cur_max);
}

cur_val |= (1<<bitPos);
cur_max = max(cur_val, cur_max);
//cout << bitPos << "_" << cur_max << endl;

vector<int> a00, a01, a10, a11;
divide(a0, a00, a01, bitPos-1);
divide(a1, a10, a11, bitPos-1);

int a0011 = 0, a0110 = 0;
if (a00.size() && a11.size()) {
a0011 = dfs(a00, a11, bitPos-1, cur_val, cur_max);
}
// else parts of the elements will be dropped
if (a01.size() && a10.size()) {
a0110 = dfs(a01, a10, bitPos-1, cur_val, cur_max);
}

if (a0011 || a0110) {
cur_max = max(max(a0011, a0110), cur_max);
return cur_max;
}
//can't divide by this bit; then merge
a0.insert(a0.end(), a1.begin(), a1.end());
a1.clear();
return dfs(a0, a1, bitPos-1, cur_val, cur_max);
}

int findMaximumXOR(vector<int>& nums) {
vector<int> nums1;
int cur_val = 0, cur_max = 0;
return dfs(nums, nums1, 31, cur_val, cur_max);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.