题解 | #百钱买百鸡问题#

这道题很好的复习了回溯，不错

#include <iostream>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector<vector<int>>result;
void backtracking(int money,vector<int>ans,int res_sum);
int main() {
    //公鸡一只5块，母鸡一只3块，小鸡三只1块
    int n;
    cin>>n;
    vector<int>ans;
    backtracking(100,ans,100);
    for(auto & i : result){
        for(int j = 0;j<3;j++){
            cout<<i[j]<<" ";
        }
        cout<<endl;
    }
}
void backtracking(int money,vector<int>ans,int res_sum){
    if(ans.size()==3){
        if(money==0&&res_sum==0){
            result.push_back(ans);
        }
        return;
    }
    int n = ans.size();
    if(n==0){//先装公鸡
        for(int i = 0;5*i<=money;i++){
            ans.push_back(i);
            money -= 5*i;
            res_sum -= i;
            backtracking(money, ans, res_sum);
            res_sum += i;
            money += 5*i;
            ans.pop_back();
        }
    }
    else if(n==1){//该装母鸡了
        for(int i=0;3*i<=money;i++){
            ans.push_back(i);
            money -= 3*i;
            res_sum -= i;
            backtracking(money, ans, res_sum);
            res_sum += i;
            money += 3*i;
            ans.pop_back();
        }
    }
    else if(n==2){//该装小鸡了
        for(int i =0;i<=money*3;i+=3){
            ans.push_back(i);
            money -= i/3;
            res_sum -=i;
            backtracking(money, ans, res_sum);
            res_sum +=i;
            money += i/3;
            ans.pop_back();
        }
    }
}
// 64 位输出请用 printf("%lld")