473. 火柴拼正方形 搜索

473. 火柴拼正方形

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

如果你能使这个正方形，则返回 true ，否则返回 false 。

思路：

首先一定要注意到这个题要所有的火柴都要用上，那么所有火柴的长度一定是4的倍数,即sum%4==0。

那么每一跟火柴的长度 len=sum/4

对于每条边，我都试着把一根火柴放进去，如果这条边的长度没有超过len，那么就满足，枚举下一根火柴。

如果大于len则返回FALSE；

class Solution {
public:
    bool dfs(int index,vector<int> mat,vector<int> &edges,int len){
        if(index==mat.size()) return true;
        for(int i=0;i<edges.size();i++){
            edges[i]+=mat[index];
            if(edges[i]<=len&&dfs(index+1,mat,edges,len)){
                return true;
            }
             edges[i]-=mat[index];//恢复现场
        }
        return false;
    }
    bool makesquare(vector<int>& mat) {
        //题目的意思是用所有的火柴，合成正方形
        int sum=0;
        for(int i=0;i<mat.size();i++){
            sum+=mat[i];
        }
        int len=sum/4;
        if(sum%4!=0) return false;
        sort(mat.begin(),mat.end(),[&](int a,int b){
            return a>b;
        });
        vector<int> edges(4);
        return dfs(0,mat,edges,len);
    }
};

类似的题目：

派蒙游戏世界对旅行荧妹很不友好

题目大意：

派蒙最近总是和旅行者在玩游戏，这个游戏共有 nnn 轮，在第 iii 轮获胜的人会获得 iii 分，没有平局。

现在给出派蒙和旅行者的得分，请问是否有一种方案符合当前得分。

换句话说就是 给定两个数 a,b 问是否存在使用1~n的数组合，和为a和b。

思路：

和上面的题目类似；从大的开始枚举如果没有超过需要的和，那么就可以放进去。就是能放就放的原则。

不能放就跳过。

在这个题目一定有解的。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
signed main(){
    int a,b;
    cin>>a>>b;
    int n=sqrt((a+b)*2);
    if((n+1)*n!=(a+b)*2){
        cout<<"NO"<<endl;
        return 0;
    }
    cout<<"YES"<<endl;
    cout<<n<<endl;
    for(int i=n;i>=1;i--){
        if(a>=i) {
            a-=i;
            cout<<i<<" ";
        }
    }
    return 0;
}