從數字集合 {1,2,3,4,5,6,7} 中選取 7 位數字組成排列，滿足：
for (i = 1234567; i <= 1400000; i++) { // 遍歷範圍
// 分解各位數字到數組 arr[0..6]
// 檢查條件：差值、不含 0/8/9、無重復
}
雖可行，但遍歷 165,433 個數字並分解位運算效率較低，且重復檢查邏輯冗餘。
#include
#include
bool used[8]; // 1-7 使用標記
int path[7]; // 當前路徑
int count = 0;
void dfs(int pos) {
if (pos == 7) { // 找到完整排列
for (int i = 0; i < 7; i++) printf("%d", path[i]);
printf("\n");
count++;
return;
}
for (int digit = 1; digit <= 7; digit++) {
if (!used[digit]) {
if (pos == 0) { // 首位必須為 1
if (digit != 1) continue;
} else {
int diff = path[pos-1] - digit;
if (diff < -2 || diff > 2) continue; // 相鄰差 > 2
}
used[digit] = true;
path[pos] = digit;
dfs(pos + 1);
used[digit] = false;
}
}
}
int main() {
dfs(0);
printf("Total: %d\n", count);
return 0;
}
| 方法 | 時間複雜度 | 搜索空間 | 適用場景 |
|---|---|---|---|
| 暴力遍歷+分解 | O(Range × D) | ~16萬 | 範圍小、一次性腳本 |
| 回溯剪枝 | O(Valid Permutations) | 極小（提前剪枝） | ✅ 推薦：標準排列組合問題 |
| 動態規劃+狀態壓縮 | O(n × 2^n) | 7 × 128 = 896 | 求計數而非列舉時極快 |
int dp[8][1<<8]; // dp[last_digit][mask] = 方案數
dp[1][1<<1] = 1; // 從 1 開始
for (int mask = 0; mask < (1<<8); mask++) {
for (int last = 1; last <= 7; last++) {
if (dp[last][mask] == 0) continue;
for (int next = 1; next <= 7; next++) {
if (mask & (1< 2) continue;
dp[next][mask | (1< 從暴力枚舉到回溯剪枝再到狀態壓縮 DP，體現了算法設計**由具體到抽象、由列舉到計數**的思維升級。
