leetcode473 Matchsticks to Square

一开始想求所有结果为target的组合来着，但是所选元素不能重叠。用这个递归思想很简单，分成四个桶，每次把元素放在任意一个桶里面，最后如果四个桶相等就可以放进去，有一个地方可以剪枝，假如任意一个桶的元素和大于了target果断return。另一个优化的点在于，如果要求能不能也就是找到一个就可以的话，那么从大到小的找可以减少回溯的次数，否则会超时。学会了一个sort函数从大到小排序的新方法。sort（nums.rbegin(),nums.rend()）; leetcode不能用sort（，，cmp）的那种方法不知道为什么。

#include<bits/stdc++.h>

using namespace std;

class Solution {

private:

    vector<int>ans;

    vector<vector<int>>res;

    vector<bool>used;

    bool cmp(int a, int b)

    {

        return a > b;

    }

    bool permutation(vector<int>nums, int index, int n,int a,int b,int c,int d)

    {

        if (a>n/||b>n/||c>n/||d>n/)

            return false;

        if (index==nums.size()&&a==b&&c==d&&b==c)

        {

            return true;

        }

        return permutation(nums, index + , n, a + nums[index], b, c, d) || permutation(nums, index + , n, a, b + nums[index], c, d) || permutation(nums, index + , n, a, b, c + nums[index], d) || permutation(nums, index + , n, a, b, c, d + nums[index]);

    }

public:

    bool makesquare(vector<int>& nums) {

        if (nums.size() == )

            return false;

        int sum=;

        int i;

        sort(nums.rbegin(),nums.rend());

        for (i = ; i < nums.size(); i++)

        {

            sum += nums[i];

        }

        if (sum %  != ||nums[nums.size()-]>sum/)

            return false;

        return permutation(nums, , sum,,,,);

    }

};

巴特西

leetcode473 Matchsticks to Square

最新文章

热门文章