问题：
求由n个字符构成，按照字母序排序后，第k个happy string。
happy string定义：
[‘a‘, ‘b‘, ‘c‘].
s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).
如："abc", "ac", "b", "abcbabcbcb"
不是happy string的例子："aa", "baa", "ababbc"
Example 1: Input: n = 1, k = 3 Output: "c" Explanation: The list ["a", "b", "c"] contains all happy strings of length 1. The third string is "c". Example 2: Input: n = 1, k = 4 Output: "" Explanation: There are only 3 happy strings of length 1. Example 3: Input: n = 3, k = 9 Output: "cab" Explanation: There are 12 different happy string of length 3 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]. You will find the 9th string = "cab" Example 4: Input: n = 2, k = 7 Output: "" Example 5: Input: n = 10, k = 100 Output: "abacbabacb" Constraints: 1 <= n <= 10 1 <= k <= 100
解法：Backtracking（回溯算法）
代码参考：
1 class Solution { 2 public: 3 void backtrack(string& res, int pos, string path, int& n, int& k) { 4 if(path.length() == n){ 5 k--; 6 if(k==0){ 7 res=path; 8 } 9 return; 10 } 11 for(int i=0; i<3; i++) { 12 char cur = ‘a‘+i; 13 if(‘a‘+i==path.back()) continue; 14 backtrack(res, pos+1, path+cur, n, k); 15 if(k==0) return; 16 } 17 return; 18 } 19 string getHappyString(int n, int k) { 20 string res(""); 21 backtrack(res, 0, string(""), n, k); 22 return res; 23 } 24 };
1415. The k-th Lexicographical String of All Happy Strings of Length n
原文：https://www.cnblogs.com/habibah-chang/p/14395008.html