P(n,r) = n!/(n-r)!。C(n,r) = n!/(r!(n-r)!)。P(n,n) = n!。public class BitmaskPermComb {
// 全排列:遍歷 0 ~ (1<
優點: 思路直觀、無遞歸堆疊溢位風險。
缺點: 時間複雜度 O(n·2^n),n>20 時極慢;不產生字典序。
public class BacktrackPerm {
private static boolean[] used;
private static int[] path;
private static int[] nums;
public static void permute(int[] a) {
nums = a; used = new boolean[a.length]; path = new int[a.length];
dfs(0);
}
private static void dfs(int depth) {
if (depth == nums.length) {
System.out.println(Arrays.toString(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path[depth] = nums[i];
dfs(depth + 1);
used[i] = false; // 回溯
}
}
}
public class BacktrackComb {
public static void combine(int[] a, int k) {
combineHelper(a, k, 0, new ArrayList<>());
}
private static void combineHelper(int[] a, int k, int start, List path) {
if (path.size() == k) {
System.out.println(path);
return;
}
// 剪枝:剩餘元素不足填滿 k
for (int i = start; i <= a.length - (k - path.size()); i++) {
path.add(a[i]);
combineHelper(a, k, i + 1, path);
path.remove(path.size() - 1);
}
}
}
public class UnifiedBacktrack {
// 全排列
public List> permute(int[] nums) {
List> res = new ArrayList<>();
backtrackPerm(nums, new boolean[nums.length], new ArrayList<>(), res);
return res;
}
private void backtrackPerm(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]);
backtrackPerm(nums, used, path, res);
path.remove(path.size()-1); used[i] = false;
}
}
// 組合
public List> combine(int n, int k) {
List> res = new ArrayList<>();
backtrackComb(n, k, 1, new ArrayList<>(), res);
return res;
}
private void backtrackComb(int n, int k, int start, List path, List> res) {
if (path.size() == k) { res.add(new ArrayList<>(path)); return; }
for (int i = start; i <= n - (k - path.size()) + 1; i++) {
path.add(i); backtrackComb(n, k, i+1, path, res); path.remove(path.size()-1);
}
}
}
public class DPComb {
/** 迭代生成所有組合 C(n,k) — 底層用「下一個組合」算法 */
public static List> combineIter(int n, int k) {
List> res = new ArrayList<>();
int[] comb = new int[k];
for (int i = 0; i < k; i++) comb[i] = i + 1; // 初始 1,2,..,k
while (true) {
res.add(Arrays.stream(comb).boxed().collect(Collectors.toList()));
// 產生下一個組合
int i = k - 1;
while (i >= 0 && comb[i] == n - k + i + 1) i--;
if (i < 0) break;
comb[i]++;
for (int j = i + 1; j < k; j++) comb[j] = comb[j-1] + 1;
}
return res;
}
/** 迭代生成全排列 — 字典序下一個排列 (std::next_permutation) */
public static List> permuteIter(int[] a) {
List> res = new ArrayList<>();
int[] arr = Arrays.copyOf(a, a.length);
Arrays.sort(arr); // 必須從最小字典序開始
do {
res.add(Arrays.stream(arr).boxed().collect(Collectors.toList()));
} while (nextPermutation(arr));
return res;
}
/** 字典序下一個排列 */
private static boolean nextPermutation(int[] a) {
int i = a.length - 2;
while (i >= 0 && a[i] >= a[i+1]) i--;
if (i < 0) return false;
int j = a.length - 1;
while (a[j] <= a[i]) j--;
swap(a, i, j);
reverse(a, i+1, a.length-1);
return true;
}
private static void swap(int[] a, int i, int j) { int t=a[i]; a[i]=a[j]; a[j]=t; }
private static void reverse(int[] a, int l, int r) { while(l
| 演算法 | 時間複雜度 | 空間複雜度 | 輸出順序 | 適用場景 |
|---|---|---|---|---|
| 位元狀態 | O(n·2^n) | O(1) 額外 | 二進制序 | n≤15、教學展示、位運算練習 |
| 遞歸回溯 | O(P(n,k)或C(n,k)) | O(k) 堆疊 | 字典序 | 通用、面試、需剪枝、需收集結果 |
| 迭代 (next_perm/comb) | O(輸出大小) | O(k) | 字典序 | 大量資料、記憶體受限、需暫停/繼續 |
// 排列含重複:排序後跳過相同未使用元素
Arrays.sort(nums);
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
// 組合含重複:同理,start 循環中跳過
if (i > start && nums[i] == nums[i-1]) continue;
CombinatoricsUtils、Guava Collections2.permutations、自行實作 Spliterator 整合 Stream API。掌握這三大類演算法,從位元操作的巧思、遞歸回溯的通用框架、到迭代生成的工程化落地,即可應對所有排列組合計算需求。