回溯法也稱為試探法,該方法首先暫時放棄關於問題規模大小的限制,並將問題的候選解按某種順序逐一枚舉和檢驗。在回溯法中,放棄當前候選解,尋找下一個候選解的過程稱為回溯。
本實例是用回溯法輸出n個自然數中以r個數全排列。代碼如下:
<?XML:namespace prefix = o ns = "urn:schemas-microsoft-com:office:Office" />
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 = s + Convert.ToString(a[j]) + ",";
}
// Memo1.Lines.Append(Trim(s));
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;
}
}