題目：
從1到n中選k個數(shù)進行排列

首先我們看這段代碼：

#include <iostream> using namespace std; int n, k; const int N = 1010; int a[N]; bool st[N];void dfs(int u) {if (u == k + 1) {for (int i = 1; i <= k; i++) {cout << a[i] << " ";}cout << endl;return ;}for (int i = 1; i <= n; i++) {if (!st[i]) {st[i] = true;a[u] = i;dfs(u + 1);st[i] = false;}} }int main() {cin >> n >> k;dfs(1);return 0; }

這段代碼，把return去掉是不會有任何問題的，現(xiàn)在我們來看下面這段代碼：

#include <iostream> using namespace std; int n, k; const int N = 1010; int a[N]; bool st[N];void dfs(int u) {if (u > k + 1) {for (int i = 1; i <= k; i++) {cout << a[i] << " ";}cout << endl;return ;}for (int i = 1; i <= n; i++) {if (!st[i]) {st[i] = true;a[u] = i;dfs(u + 1);st[i] = false;}} }int main() {cin >> n >> k;dfs(1);return 0; }

這段代碼如果我們把return去掉，就會出現(xiàn)結果不對的問題，原因是什么呢？？？
是終止條件的不同。

第一個代碼的條件是u==k+1,而第二個代碼的條件是u >k+1,那么當我們都把return 去掉時，第二個代碼中的

for (int i = 1; i <= n; i++) {if (!st[i]) {st[i] = true;a[u] = i;dfs(u + 1);st[i] = false;}

此時繼續(xù)dfs，那么u繼續(xù)+1,舉個例子，本來u=2，k = 1,u已經比k大了，輸出一次結果，此時你不回溯，那么for循環(huán)繼續(xù)，u+1，u = 3，u還是比k大，那么又會重新打印剛剛的結果，可是第一種情況，因為你的判斷條件是u==k+1,u = 2，k = 1,符合條件，此時如果不回溯，u+1,u = 3，u!=k+1,就不會重新打印結果，所以最后答案是一樣的，但是事實上dfs的次數(shù)變多了。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的dfs中return回溯问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。