Java排列组合详解（从零开始掌握排列组合算法）

二、Java实现排列（递归回溯法）

我们使用递归 + 回溯的方式来生成所有排列。核心思想是：每次从剩余元素中选择一个加入当前路径，递归处理剩下的元素，完成后回退（回溯）。

import java.util.*;public class PermutationExample {    public static void main(String[] args) {        int[] nums = {1, 2, 3};        List<List<Integer>> result = new ArrayList<>();        boolean[] used = new boolean[nums.length];        backtrack(nums, new ArrayList<>(), used, result);                System.out.println("所有排列结果：");        for (List<Integer> perm : result) {            System.out.println(perm);        }    }    // 回溯函数    private static void backtrack(int[] nums, List<Integer> path,                                  boolean[] used, List<List<Integer>> result) {        // 递归终止条件：路径长度等于数组长度        if (path.size() == nums.length) {            result.add(new ArrayList<>(path)); // 注意要拷贝            return;        }                for (int i = 0; i < nums.length; i++) {            if (used[i]) continue; // 已使用则跳过                        path.add(nums[i]);            used[i] = true;            backtrack(nums, path, used, result); // 递归                        // 回溯：撤销选择            path.remove(path.size() - 1);            used[i] = false;        }    }}  

运行结果：

[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1]  

三、Java实现组合（固定长度）

组合的关键在于“不重复”且“不考虑顺序”。我们通常通过控制起始索引来避免重复选择前面的元素。

import java.util.*;public class CombinationExample {    public static void main(String[] args) {        int[] nums = {1, 2, 3, 4};        int k = 2; // 选2个        List<List<Integer>> result = new ArrayList<>();        combine(nums, k, 0, new ArrayList<>(), result);                System.out.println("所有组合结果（选" + k + "个）：");        for (List<Integer> comb : result) {            System.out.println(comb);        }    }    private static void combine(int[] nums, int k, int start,                                List<Integer> path, List<List<Integer>> result) {        // 终止条件：路径长度达到k        if (path.size() == k) {            result.add(new ArrayList<>(path));            return;        }                // 从start开始遍历，避免重复        for (int i = start; i < nums.length; i++) {            path.add(nums[i]);            combine(nums, k, i + 1, path, result); // 下一层从i+1开始            path.remove(path.size() - 1); // 回溯        }    }}  

运行结果：

[1, 2][1, 3][1, 4][2, 3][2, 4][3, 4]  

四、常见应用场景

• 密码暴力破解（生成所有可能的字符排列）
• 抽奖系统（从用户池中随机抽取若干人，本质是组合）
• 算法竞赛中的搜索题（如N皇后、数独等）
• 数据分析中的特征组合（机器学习预处理）

五、总结

通过本教程，你已经掌握了如何用Java实现排列和Java实现组合。核心技巧是递归 + 回溯，关键在于理解“选择-递归-撤销”的过程。记住：

• 排列关注顺序，需记录哪些元素已使用（used数组）
• 组合不关注顺序，通过控制起始索引避免重复

希望这篇排列组合算法教程能帮助你打下坚实的算法基础！动手敲一遍代码，你会理解得更深刻。

提示：实际项目中若数据量较大，需考虑性能优化或使用迭代方法避免栈溢出。