面试算法题：如何生成给定字符串长度为k的无重复排列？

你的问题很典型——在生成排列时没控制字符的复用，导致重复结果出现。我来帮你梳理下问题根源和可行的解决方案：

问题根源 #

你之前的循环遍历方法之所以会产生重复，核心原因是没有标记已经被选入当前序列的字符，导致同一个字符在不同的循环分支里被重复选取，甚至在同一个排列里多次出现，最终生成不符合要求的重复结果或无效排列。

经典解决方案：回溯法（Backtracking） #

回溯法是解决这类排列组合问题的标准思路，通过"选择-递归-回溯"的流程，确保每个字符在单个排列中只被使用一次，同时遍历所有可能的排列组合。

实现思路 #

• 维护一个正在构建的临时字符串current，用来存储当前的排列片段
• 用一个布尔数组used标记原字符串中哪些字符已经被选入current，避免重复使用
• 当current的长度等于k时，将其加入结果集合
• 遍历原字符串的每个字符：
  1. 如果该字符未被使用，标记为已使用并加入current
  2. 递归调用函数继续构建下一个字符
  3. 递归返回后，撤销本次选择（从current移除字符，取消used标记），让后续分支可以重新使用该字符

C++代码示例 #

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

// 回溯辅助函数
void backtrack(const string& s, int k, string& current, vector<bool>& used, vector<string>& result) {
    // 终止条件：当前序列长度达到k，加入结果
    if (current.size() == k) {
        result.push_back(current);
        return;
    }

    for (int i = 0; i < s.size(); ++i) {
        // 跳过已使用的字符
        if (!used[i]) {
            // 选择当前字符
            used[i] = true;
            current.push_back(s[i]);
            
            // 递归构建下一个位置
            backtrack(s, k, current, used, result);
            
            // 回溯：撤销选择
            current.pop_back();
            used[i] = false;
        }
    }
}

vector<string> findKLengthPermutations(string s, int k) {
    vector<string> result;
    // 边界情况处理：k无效时直接返回空结果
    if (k <= 0 || k > s.size()) {
        return result;
    }

    string current;
    vector<bool> used(s.size(), false);
    backtrack(s, k, current, used, result);
    return result;
}

代码解释 #

• used数组是关键：它确保每个字符在单个排列中只会被选中一次，从根源上避免了重复排列和无效的重复字符组合
• 回溯步骤不可少：递归返回后必须撤销选择，这样才能让其他分支有机会使用这个字符，保证所有可能的排列都被遍历到

额外补充：处理原字符串含重复字符的情况 #

如果你的输入字符串本身包含重复字符（比如"aab"），想要生成无重复的排列，只需要在循环时跳过与当前字符相同且前一个相同字符未被使用的情况（避免重复分支）。不过根据你的问题描述，输入字符串的字符是不重复使用的，所以上面的代码已经足够解决你的问题。

内容的提问来源于stack exchange，提问作者Oliver Blue