如何生成任意长度无重复数组的全排列，要求无重复元素且长度与原数组一致

核心思路 #

使用回溯法实现，逻辑如下：

• 逐层固定数组当前索引位的元素，递归处理后续索引位的排列
• 递归到数组末尾时，记录当前排列结果
• 递归返回后回溯交换元素，复位状态用于生成其他排列
  因为原数组本身无重复元素，该逻辑生成的所有排列天然不存在重复元素，且长度与原数组完全一致，不会产生非法结果。

Java 实现代码 #

import java.util.ArrayList;
import java.util.List;

public class PermutationGenerator {
    public List<String> generateAllCombinations(String[] list) {
        List<String> result = new ArrayList<>();
        backtrack(list, 0, result);
        return result;
    }

    private void backtrack(String[] list, int currentIndex, List<String> result) {
        // 递归终止条件：当前索引等于数组长度，说明已生成一个完整排列
        if (currentIndex == list.length) {
            StringBuilder sb = new StringBuilder();
            for (String s : list) {
                sb.append(s);
            }
            result.add(sb.toString());
            return;
        }
        for (int i = currentIndex; i < list.length; i++) {
            // 交换当前位和i位元素，固定currentIndex位置的元素为list[i]
            swap(list, currentIndex, i);
            // 递归处理下一位
            backtrack(list, currentIndex + 1, result);
            // 回溯，交换回原位置
            swap(list, currentIndex, i);
        }
    }

    private void swap(String[] list, int a, int b) {
        String temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }

    // 测试示例
    public static void main(String[] args) {
        PermutationGenerator generator = new PermutationGenerator();
        String[] list = {"A", "B", "C"};
        List<String> permutations = generator.generateAllCombinations(list);
        for (String p : permutations) {
            System.out.println(p);
        }
    }
}

运行结果 #

输入String[] list = {"A","B","C"}运行后输出如下：

ABC
ACB
BAC
BCA
CAB
CBA

复杂度说明 #

• 时间复杂度：O(n!)，n为数组长度，共生成n!个排列，每个排列需要O(n)时间拼接字符串
• 空间复杂度：O(n)，递归栈深度为n，无额外辅助存储空间

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