2023.3.25

搜索

P2089烤鸡

有10种配料，每一种配料都有三种可能：1g, 2g, 3g

所以——所有可能的种类是3^10个=59049个

int a[11];
int res[60000][11];
int cnt=0;

void dfs(int layer,int left){
    int i;
    if(index==11){//找到了最后一个
        if(left==0){
            for(int i=1;i<=10;i++)res[cnt][i]=a[i];
            cnt++;
        }
    }else{
        for(int i=1;i<=3&&i<=left;i++){
            a[layer]=i;
            dfs(layer+1,left-i);
        }
    }
}

int main(){
    int n;
    cin>>n;
    if(n>=10||n<=30){//才能正常输出
        dfs(1,n);//第1层，还剩n g
    }else{cout<<0;}
}

P1706 全排列

回溯

bool used[10]={0};
int a[10];
int n;    
void  f(int k){
    if(k==n+1){
        for(int i=1;i<=n;i++){cout<<setw(5)<<left<<a[i];}
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++){
        if(!used[i]){//没有被用过
            a[k]=i;
            used[i]=true;
            f(k+1);
            used[i]=false;//very important,回溯要消除前面关于used[i]=true。
        }
    }
}

int main(){
    cin>>n;
    f(1);
}