字符串排列组合

问题

给定一个字符串，输出它的所有排列组合。例如输入 "abc"，输出 ["abc", "acb", "bac", "bca", "cab", "cba"]。

解答

基础版：回溯法

function permute(str) {
  const result = [];
  const chars = str.split('');
  
  function backtrack(path, used) {
    // 当路径长度等于字符串长度，得到一个排列
    if (path.length === chars.length) {
      result.push(path.join(''));
      return;
    }
    
    for (let i = 0; i < chars.length; i++) {
      // 跳过已使用的字符
      if (used[i]) continue;
      
      // 选择当前字符
      path.push(chars[i]);
      used[i] = true;
      
      // 递归
      backtrack(path, used);
      
      // 撤销选择
      path.pop();
      used[i] = false;
    }
  }
  
  backtrack([], []);
  return result;
}

// 测试
console.log(permute('abc'));
// ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

处理重复字符

function permuteUnique(str) {
  const result = [];
  const chars = str.split('').sort(); // 排序，让相同字符相邻
  
  function backtrack(path, used) {
    if (path.length === chars.length) {
      result.push(path.join(''));
      return;
    }
    
    for (let i = 0; i < chars.length; i++) {
      if (used[i]) continue;
      
      // 剪枝：跳过重复字符
      // 当前字符与前一个相同，且前一个未被使用，说明会产生重复
      if (i > 0 && chars[i] === chars[i - 1] && !used[i - 1]) {
        continue;
      }
      
      path.push(chars[i]);
      used[i] = true;
      backtrack(path, used);
      path.pop();
      used[i] = false;
    }
  }
  
  backtrack([], []);
  return result;
}

// 测试
console.log(permuteUnique('abb'));
// ['abb', 'bab', 'bba']

交换法

function permuteBySwap(str) {
  const result = [];
  const chars = str.split('');
  
  function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  
  function backtrack(start) {
    if (start === chars.length) {
      result.push(chars.join(''));
      return;
    }
    
    const used = new Set(); // 记录当前层已使用的字符
    
    for (let i = start; i < chars.length; i++) {
      // 去重：同一层不选择相同字符
      if (used.has(chars[i])) continue;
      used.add(chars[i]);
      
      swap(chars, start, i);
      backtrack(start + 1);
      swap(chars, start, i); // 换回来
    }
  }
  
  backtrack(0);
  return result;
}

// 测试
console.log(permuteBySwap('abc'));
// ['abc', 'acb', 'bac', 'bca', 'cba', 'cab']

关键点

• 回溯模板：选择 → 递归 → 撤销选择
• used 数组：标记哪些字符已被使用，避免重复选取
• 去重技巧：先排序，跳过 chars[i] === chars[i-1] && !used[i-1] 的情况
• 时间复杂度：O(n × n!)，n! 个排列，每个排列需要 O(n) 时间构建
• 交换法：原地操作，空间更优，但顺序与回溯法不同