已知一个数组，保存了n个(n<=15)火柴棍，问可否使用这n个火柴棍摆成1个正方形?
LeetCode 473. Matchsticks to Square
无优化的深度搜索
算法：
想象正方形的4条边即为4个桶，将每个火柴杆回溯的放置在每个桶中，在放 完n个火柴杆后，检查4个桶中的火柴杆长度和是否相同，相同返回真，否 则返回假;在回溯过程中，如果当前所有可能向后的回溯，都无法满足条 件，即递归函数最终返回假。
优化与剪枝：
优化1:n个火柴杆的总和对4取余需要为0，否则返回假。
优化2:火柴杆按照从大到小的顺序排序，先尝试大的减少回溯可能。
优化3:每次放置时，每条边上不可放置超过总和的1/4长度的火柴杆。
class Solution{
public:
bool make square(std::vector<int> &nums){
if(noms.size() < 4){
return false;//数量小于4返回假
}
int sum = 0;
for(int i =0; i<nums.size();i++){
sum += nums[i];//累加求和
}
if( sum% 4){
return false;
}
std::sort(nums.rbegin(),nums.rend());//逆序，从大到小排列
int bucket[4] = {0};
return generate(0, noms, sum / 4, bucket);
}
private:
bool generate(int i ,std::vector<int> &nums, int target, int bucket[]){
if(i >= nums.size()){
return bucket[0] == target && bucket[1] == target && bucket[2] && bucket[3] == target;
}
for(int j= 0; j < 4; j++){
if( bucket[j] + nums > target){
continue;
}
bucket[j] += nums[i];
if(generate(i+1, nums, target, bucket)){
return true;
}
bucket[j] -= nums[i];
}
return false;
}
};
位运算法
1.使用位运算法，构造出所有和为target(总和/ 4)的子集，存储在向量ok_subset中，这 些是候选的边组合。
2.遍历所有的ok_subset，两两进行对比，如果ok_set[i]和ok_set[j]进行与运算的结果为 0，则说明ok_set[i]和ok_set[j]表示的是无交集的两个集合(没有选择同样的火柴棍)，这 两个集合可以代表两个可以同时存在的满足条件的边;将ok_set[i]与ok_set[j]求或，结 果存储在ok_half中，它代表所有满足一半结果的情况。
3.遍历所有的ok_half，两两进行对比，如果ok_half[i]和ok_half[j]进行与运算的结果为0 ，则返回true(说明有4个满足条件的边，即可组成正方形);否则返回false。
