A1103-Integer Factorization

递归一直不太好。。。
细节还挺多的

#include<bits/stdc++.h>
using namespace std;
int num,K,P;
int maxFacSum=-1;
vector<int> fact,temp,ans;
int power(int x) //x是指数 
{
    int ans=1;   //细节考虑到为0的情况 
    for(int i=0;i<P;i++) 
    {
        ans=ans*x;
    }
    return ans;  
}
void DFS(int index,int sum,int nowK,int facSum)
{
    if(sum==num&&nowK==K)
    {
        if(facSum>maxFacSum)
        {
            maxFacSum=facSum;
            ans=temp;
        }
        return;
    }
        
    if(sum>=num||nowK>K)
        return;
    if(index>0)
    {
        temp.push_back(index);            //能选上 
        DFS(index,sum+fact[index-1],nowK+1,facSum+index);
        temp.pop_back();                 //为什么要pop
                                         //因为若是不成立就不能要这个数就不能选
                                         //若是成立，ans已经记录改组，下一组要换数了
                                         //若是还不够要继续递归 
        DFS(index-1,sum,nowK,facSum);
    }
 } 
int main()
{
    scanf("%d %d %d",&num,&K,&P);
    int tmp=1,i=1;
    while(tmp<=num)
    {
        fact.push_back(tmp);
        tmp=power(++i);     
    } 
    //cout<<fact.size();
    DFS(fact.size(),0,0,0);
    if(maxFacSum==-1)
        printf("Impossible\n");
    else
    {
        printf("%d = %d^%d",num,ans[0],P);   //为什么ans[0]一定有值 
        for(int i=1;i<ans.size();i++)
            printf(" + %d^%d",ans[i],P);
    }
    return 0;
}