给你n个a,m个z组成的所有可能的字符串，并将字符串按照字典序从小到大排列输出第k个字符串

写在前面

一道笔试编程题

题目要求

解法

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    string findK(int n,int m,int k) {
        string res;
        if(n<0||m<0||k<=0) return to_string(-1);
        int num = countnum(n,m);
        if(k>num) return to_string(-1);
        int count = 1;
        helper(n,m,k,count,res);
        return res;
    }
    //求c(n+m,n)
    int countnum(int n,int m) {
        if(n==0||m==0) return 1;
        int t = 1,count = n;
        while(count>0) {
            t *= count + m;
            --count;
        }
        int temp = 1;
        while(n) {
            temp *= n;
            --n;
        }
        return t/temp;
    }

    bool helper(int n,int m,int k,int& count,string& res) {
        if(n==0&&m==0) {
            if(count==k) return true;
            else {
                //cout << res << endl;
                ++count;
            }
        }

        if(n>0) {
            res += 'a';
            if(helper(n-1,m,k,count,res)) return true;
            else res.pop_back();
        }
        if(m>0) {
            res += 'z';
            if(helper(n,m-1,k,count,res)) return true;
            else res.pop_back();
        }
        return false;
    }
};


int main() {
    int n =0,m = 0, k = 0;
    cin >> n >> m >> k;
    Solution s;
    cout << s.findK(n,m,k) << endl;
    return 0;
}

分析：采用递归的方式按照字典顺序构造字符串，采用回溯的方式，当构造到第k个的时候整体递归返回不再继续回溯。
注意点：对于输入参数的合法性判断，当k大于总可能个数的时候直接返回-1。
总可能数是c(m+n,n) 相当于先取n个a占据n+m个位置当中的n个剩下的全部放z。
c(n+m,n) = (n+m)(n+m-1)…*(m+1) / n!
对于回溯求解字符串排列组合时需要就地进行现场还原，当添加了一个字符的时候递归返回的时候需要pop_back掉这个字符之后再进行下一次的可能尝试。
时间复杂度为o((n+m)*k)