Java 實現排列組合的三大核心算法：位狀態、遞歸回溯與動態規劃

排列組合是演算法面試與業務開發中的高頻題型。本文系統梳理三種主流實現思路，附完整可運行代碼，並分析時間空間複雜度與適用場景。

一、二進制狀態法（位掩碼枚舉）

核心思想： 利用整數的二進制位表示元素的「選/不選」狀態。對於 n 個元素，遍歷 0 ~ 2^n - 1，每個數字的二進制位對應一種組合。

優點： 思路直觀，代碼簡潔；缺點： 時間複雜度 O(n·2^n)，僅適合 n ≤ 20 的小規模數據。

public class BitMaskCombination {
    public static void printCombinations(int[] nums) {
        int n = nums.length;
        int total = 1 << n; // 2^n
        for (int mask = 1; mask < total; mask++) { // 從1開始排除空集
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    sb.append(nums[i]).append(' ');
                }
            }
            System.out.println(sb.toString().trim());
        }
    }
    public static void main(String[] args) {
        printCombinations(new int[]{1, 2, 3, 4});
    }
}

二、遞歸回溯法（DFS）

核心思想： 以「決策樹」形式探索所有可能：每一步決定「選擇當前元素」或「跳過當前元素」。通過回溯撤銷選擇，實現全排列或指定大小的組合。

優點： 靈活性強，易於剪枝、加入約束條件；缺點： 函數調用開銷大，深度過大易棧溢出。

import java.util.*;

public class BacktrackCombination {
    // 求所有組合（冪集）
    public static List> combineAll(int[] nums) {
        List> res = new ArrayList<>();
        backtrackAll(nums, 0, new ArrayList<>(), res);
        return res;
    }
    private static void backtrackAll(int[] nums, int start, List path, List> res) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrackAll(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }

    // 求指定大小 k 的組合
    public static List> combineK(int[] nums, int k) {
        List> res = new ArrayList<>();
        backtrackK(nums, 0, k, new ArrayList<>(), res);
        return res;
    }
    private static void backtrackK(int[] nums, int start, int k, List path, List> res) {
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrackK(nums, i + 1, k, path, res);
            path.remove(path.size() - 1);
        }
    }

    // 全排列
    public static List> permute(int[] nums) {
        List> res = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrackPermute(nums, used, new ArrayList<>(), res);
        return res;
    }
    private static void backtrackPermute(int[] nums, boolean[] used, List path, List> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            backtrackPermute(nums, used, path, res);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println("所有組合: " + combineAll(nums));
        System.out.println("選2個組合: " + combineK(nums, 2));
        System.out.println("全排列: " + permute(nums));
    }
}

三、動態規劃/迭代構建法

核心思想： 從小規模問題推導大規模問題。例如組合數 C(n,k) = C(n-1,k) + C(n-1,k-1)，或通過迭代逐步擴展結果集。

優點： 無遞歸開銷，空間可優化；缺點： 邏輯較抽象，需仔細處理邊界。

import java.util.*;

public class IterativeCombination {
    // 迭代生成所有組合（冪集）
    public static List> subsets(int[] nums) {
        List> res = new ArrayList<>();
        res.add(new ArrayList<>()); // 空集
        for (int num : nums) {
            int size = res.size();
            for (int i = 0; i < size; i++) {
                List newSubset = new ArrayList<>(res.get(i));
                newSubset.add(num);
                res.add(newSubset);
            }
        }
        return res;
    }

    // 迭代生成全排列
    public static List> permuteIterative(int[] nums) {
        List> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int num : nums) {
            List> newRes = new ArrayList<>();
            for (List perm : res) {
                for (int i = 0; i <= perm.size(); i++) {
                    List newPerm = new ArrayList<>(perm);
                    newPerm.add(i, num);
                    newRes.add(newPerm);
                }
            }
            res = newRes;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println("冪集: " + subsets(new int[]{1, 2, 3}));
        System.out.println("全排列: " + permuteIterative(new int[]{1, 2, 3}));
    }
}

四、選型建議

進階提示： 當元素含重複值時，需在回溯或迭代前排序並加入去重判斷（if (i > start && nums[i] == nums[i-1]) continue;），避免產生重複組合/排列。