經典算法：C# 回溯法生成 n 取 r 全排列

回溯法（試探法）通過逐步構建候選解、在發現不滿足條件時撤銷上一步（回溯），最終枚舉所有可行解。本文實現從 n 個自然數中取 r 個數的全排列（排列順序敏感，不重複）。

核心代碼

public void Arrange(int n, int r)
{
    int i = 0, j;
    string s;
    int[] a = new int[n];
    a[i] = 1;
    while (true)
    {
        if ((a[i] - i) <= (n - r + 1))
        {
            if (i == (r - 1))
            {
                s = "";
                for (j = 0; j < r; j++)
                {
                    s += Convert.ToString(a[j]) + ",";
                }
                Console.WriteLine(s);
                a[i] = a[i] + 1;
                continue;
            }
            i = i + 1;
            a[i] = a[i - 1] + 1;
        }
        else
        {
            if (i == 0)
            {
                break;
            }
            i = i - 1;
            a[i] = a[i] + 1;
        }
    }
}

算法邏輯解析

• a 數組存儲當前排列，下標即位置，值為選取的數字（1~n）。
• a[i] - i <= n - r + 1 判斷當前位置是否還可遞增；否則回溯至上一位置。
• 當 i == r-1 時，已構建完 r 個數，輸出並遞增最後一位繼續搜索。
• 回溯條件：i == 0 且無法遞增時，全排列結束。

複雜度與適用場景

時間複雜度 O(P(n,r))，空間 O(r)。適合 n、r 較小（如 n≤10）的全排列生成；大規模場景建議採用迭代器或啟發式剪枝優化。