Java 全排列與組合算法實現：二進制狀態、遞歸與動態規劃三種方案

方案一：二進制狀態枚舉（適合小數據量）

利用整數二進制位表示選擇狀態，遍歷 0 到 2^n-1，按位檢查生成組合。

public class BinaryPermutation {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7,8,9};
        int n = nums.length;
        for (int i = 1; i < (1 << n); i++) { // 從 1 開始排除空集
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) sb.append(nums[j]);
            }
            System.out.println(sb);
        }
    }
}

方案二：遞歸回溯（通用、代碼量較大）

import java.util.*;

public class RecursiveCombination {
    // 全排列
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrackPermute(nums, new ArrayList<>(), new boolean[nums.length], res);
        return res;
    }
    private static void backtrackPermute(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> 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, path, used, res);
            path.remove(path.size()-1); used[i] = false;
        }
    }

    // 組合 C(n,k)
    public static List<List<Integer>> combine(int[] nums, int k) {
        List<List<Integer>> res = new ArrayList<>();
        backtrackCombine(nums, k, 0, new ArrayList<>(), res);
        return res;
    }
    private static void backtrackCombine(int[] nums, int k, int start, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == k) { res.add(new ArrayList<>(path)); return; }
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrackCombine(nums, k, i+1, path, res);
            path.remove(path.size()-1);
        }
    }
}

方案三：動態規劃/迭代構建（高效、無遞歸棧溢出風險）

public class DPCombination {
    // 所有子集（冪集）
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>()); // 空集
        for (int num : nums) {
            int size = res.size();
            for (int i = 0; i < size; i++) {
                List<Integer> newSub = new ArrayList<>(res.get(i));
                newSub.add(num);
                res.add(newSub);
            }
        }
        return res;
    }

    // 指定大小組合 C(n,k) - 迭代版
    public static List<List<Integer>> combineIter(int[] nums, int k) {
        List<List<Integer>> res = new ArrayList<>();
        int[] indices = new int[k];
        for (int i = 0; i < k; i++) indices[i] = i;
        while (true) {
            List<Integer> comb = new ArrayList<>();
            for (int idx : indices) comb.add(nums[idx]);
            res.add(comb);
            // 生成下一個組合索引
            int i = k - 1;
            while (i >= 0 && indices[i] == nums.length - k + i) i--;
            if (i < 0) break;
            indices[i]++;
            for (int j = i+1; j < k; j++) indices[j] = indices[j-1] + 1;
        }
        return res;
    }
}

方案對比與選型建議