Nuggets team number online, help you Offer rimmon! Click to see details

I. Topic Description:

Ii. Thinking analysis:

There are several possibilities for team assignments, two to the NTH, which is the kind of complexity that you would normally want to recursively backtrack, but it’s not necessary. Here is an alternative to recursive backtracking secrets – bit operations

Let’s say we have a team abcd, let’s use 1010 for one team: {a,c}; second team: {b,d}

So we just have to go from 0000 to 1111

So let’s look at what’s going on here,

First of all, 1010 and 0101 must be redundant, so we can cut the branches in half

The following 0000 and 1111 certainly can not be used to remove these two possibilities

That is, you only need to traverse 0001 to 1000

Well, what if you reduce the time it takes to find the minimum

We will sort the array, using the idea of bitwise operation to find the minimum value (here pause, dig friends with their own pen to see, calculate can be compared with the answer).

Iii. AC code:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int countVec(vector<int> arr, int n){
    int ret =  0;
    for(int i = 0; i <arr.size(a); i++){if((1<< i) & n ){ ret += arr[i]; }}return ret;

}


int divide_group(vector<int> arr, int n){
    int len = 1 << n - 2;// Exclude all zeros and all 1s
    int zlen = 1 << n - 1; // Because the inverse code is actually only half needed
    int sum = 0;
    / / sum
    for(int i = 0; i < n; i++){
        sum += arr[i];
    }

    sort(arr.begin(),arr.end());
    int ret = 0;

    for(int i = 1; i <= zlen; i++ ){

        int s1 = countVec(arr, i);

        int s2 = sum - s1;
        int idx = 0;
        if(s1 - s2 == 0) {continue;
        }
        int tt = s1 - s2 > 0? 1 : 0; //
        int d = i;
        while(d&1 ^ tt){
                d = d >> 1;
               // cout<< "z:" << i<< endl;
                idx++;
        }

        if(abs(s1 - s2) < 2* arr[idx]){ ret++; }}return ret;
}

int main(a){
    vector<int> arr;
    arr.push_back(5);
    arr.push_back(4);
    arr.push_back(7);
    arr.push_back(6);
    cout << divide_group(arr,4);
}
Copy the code

Iv. Summary:

In general, every time you do a backtrace, you’re going to want to pry and find the best way to get 2n ^ 2n ^ 2n ^ 2n ^ 2n ^ 2.

Remember in the end of the road to try exhaustion, don’t give up when the road ahead is long.

Dream in the front, the road at the foot.