可以使用遞歸的方式實現回溯法求全排列。具體步驟如下:
定義一個遞歸函數 backtrack()
,該函數有兩個參數:nums
表示待排列的數組,path
表示當前已經排好的部分排列。
在 backtrack()
函數中,首先判斷當前已排好的部分排列是否達到了數組的長度,如果是,則將該排列加入結果集。
如果當前部分排列還沒有達到數組的長度,遍歷數組中尚未使用的元素,將每個尚未使用的元素加入到當前部分排列的末尾,并將其標記為已使用,然后遞歸調用 backtrack()
函數繼續排列剩下的元素。
在遞歸調用結束后,需要將當前部分排列恢復到之前的狀態,即將最后一個加入的元素移除,并將其標記為未使用,以便嘗試下一個可用的元素。
最后,在主函數中調用 backtrack()
函數并傳入初始參數即可。
以下是使用遞歸回溯法實現全排列的代碼示例:
#include <stdio.h>
#include <stdbool.h>
// 數組長度
#define N 3
// 標記數組,標記元素是否已使用
bool used[N];
// 全排列結果集
int res[N];
// 回溯函數
void backtrack(int nums[], int depth) {
// 如果已排好的部分排列達到了數組的長度,輸出結果
if (depth == N) {
for (int i = 0; i < N; i++) {
printf("%d ", res[i]);
}
printf("\n");
return;
}
// 遍歷數組中尚未使用的元素
for (int i = 0; i < N; i++) {
if (!used[i]) {
// 將尚未使用的元素加入到部分排列的末尾
res[depth] = nums[i];
used[i] = true;
// 遞歸調用,繼續排列剩下的元素
backtrack(nums, depth + 1);
// 將部分排列恢復到之前的狀態,以便嘗試下一個可用的元素
used[i] = false;
}
}
}
int main() {
int nums[N] = {1, 2, 3};
backtrack(nums, 0);
return 0;
}
運行以上代碼,將得到輸出:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
以上就是使用遞歸回溯法實現全排列的方法。