C 語言全排列組合：從 1,2,3,4 中取 3 個數組成互不相同三位數的三種算法

題目：數字 {1,2,3,4} 組成互不相同、無重復的三位數，共幾個？要求三種方法。

數學答案

排列數 P(4,3) = 4 × 3 × 2 = 24 個。

方法一：三層循環暴力篩選（最直觀）

for (int i = 1; i <= 4; i++)
    for (int j = 1; j <= 4; j++)
        for (int k = 1; k <= 4; k++)
            if (i != j && i != k && j != k)
                printf("%d%d%d\n", i, j, k);

方法二：遞歸回溯 + used 數組（通用全排列模板）

int a[4] = {1,2,3,4};
int path[3];
bool used[5] = {0};

void dfs(int depth) {
    if (depth == 3) {
        for (int i = 0; i < 3; i++) printf("%d", path[i]);
        printf("\n");
        return;
    }
    for (int i = 0; i < 4; i++) {
        if (!used[a[i]]) {
            used[a[i]] = true;
            path[depth] = a[i];
            dfs(depth + 1);
            used[a[i]] = false; // 回溯
        }
    }
}

方法三：C++ STL next_permutation（工程實戰首選）

#include 
#include 
#include 
int main() {
    std::vector v = {1,2,3,4};
    std::sort(v.begin(), v.end());
    do {
        // 取前 3 位
        std::cout << v[0] << v[1] << v[2] << '\n';
    } while (std::next_permutation(v.begin(), v.end()));
}

對比總結

進階：組合數 C(4,3)=4 再全排列 3! = 6 → 24

先用組合算法選 3 個數，再對這 3 個數全排列，邏輯更清晰，代碼可復用 comb + perm 兩個通用函數。

掌握回溯模板 + used 數組 + path 數組，所有排列組合、子集、N 皇后、數獨解題通殺。