M 選 N 組合算法：遞歸/迭代實現與剪枝優化

問題定義

從 1..M 中選取 N 個數，輸出所有組合（順序無關）。例：M=4, N=2 → 12 13 14 23 24 34。M、N 由用戶輸入。

遞歸回溯法（最直觀）

void combine(int m, int n, int start, List<Integer> path, List<List<Integer>> result) {
    if (path.size() == n) {
        result.add(new ArrayList<>(path));
        return;
    }
    // 剪枝：剩餘數字不足以填滿 path
    for (int i = start; i <= m - (n - path.size()) + 1; i++) {
        path.add(i);
        combine(m, n, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}

迭代法（位掩碼，適合 M ≤ 20）

for (int mask = 0; mask < (1 << m); mask++) {
    if (Integer.bitCount(mask) == n) {
        List<Integer> comb = new ArrayList<>();
        for (int i = 0; i < m; i++)
            if ((mask >> i & 1) == 1) comb.add(i + 1);
        result.add(comb);
    }
}

下一組合算法（字典序生成，O(1) 空間）

// 初始組合 [1,2,...,n]
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = i + 1;

while (true) {
    output(a);
    // 找最右可增位
    int i = n - 1;
    while (i >= 0 && a[i] == m - n + i + 1) i--;
    if (i < 0) break;
    a[i]++;
    for (int j = i + 1; j < n; j++) a[j] = a[j - 1] + 1;
}

複雜度與選型

Java 完整示例（遞歸版）

import java.util.*;

public class Combination {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(), n = sc.nextInt();
        combine(m, n, 1, new ArrayList<>(), new ArrayList<>())
            .forEach(c -> System.out.println(c.stream().map(String::valueOf).collect(Collectors.joining())));
    }
    static List<List<Integer>> combine(int m, int n, int start, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == n) { res.add(new ArrayList<>(path)); return res; }
        for (int i = start; i <= m - (n - path.size()) + 1; i++) {
            path.add(i);
            combine(m, n, i + 1, path, res);
            path.remove(path.size() - 1);
        }
        return res;
    }
}