[已解决]如何用非递归形式做出回溯类型的题？

zhangjinxuan

比如说全排列，正常情况我们是这么做的：

1. #include <cstdio>
   
2. using namespace std;
   
3. 
   
4. int n, res[13];
   
5. bool u[13];
   
6. 
   
7. void dfs(int c) {
   
8.         if (c == n + 1) {
   
9.                 for (int i = 1; i <= n; ++i) {
   
10.                         printf("%d ", res[i]);
    
11.                 }
    
12.                 puts("");
    
13.                 return;
    
14.         }
    
15.         for (int i = 1; i <= n; ++i) {
    
16.                 if (!u[i]) {
    
17.                         u[i] = 1;
    
18.                         res[c] = i;
    
19.                         dfs(c + 1);
    
20.                         u[i] = 0;
    
21.                 }
    
22.         }
    
23. }
    
24. 
    
25. int main() {
    
26.         scanf("%d", &n);
    
27.         dfs(1);
    
28. }

复制代码

但我该怎么样把这段代码写为非递归的形式呢？

最佳答案

月排行榜 / 总排行榜

柿子饼同学

2022-10-23 11:47:13

next_permutation() 实现是就不是递归 , 可以直接用
开个玩笑
看看这个 : https://blog.csdn.net/wzh1378008099/article/details/108196039?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166649692416782412538235%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=166649692416782412538235&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-108196039-null-null.142^v59^new_blog_pos_by_title,201^v3^add_ask&utm_term=%E5%85%A8%E6%8E%92%E5%88%97%E4%B8%8D%E7%94%A8%E9%80%92%E5%BD%92&spm=1018.2226.3001.4187

跳转到最佳答案楼层

柿子饼同学

next_permutation() 实现是就不是递归 , 可以直接用
开个玩笑
看看这个 : https://blog.csdn.net/wzh1378008099/article/details/108196039?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166649692416782412538235%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=166649692416782412538235&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-108196039-null-null.142^v59^new_blog_pos_by_title,201^v3^add_ask&utm_term=%E5%85%A8%E6%8E%92%E5%88%97%E4%B8%8D%E7%94%A8%E9%80%92%E5%BD%92&spm=1018.2226.3001.4187

zhangjinxuan

柿子饼同学 发表于 2022-10-23 11:47
next_permutation() 实现是就不是递归 , 可以直接用
开个玩笑
看看这个 : https://blog.csdn.net/wzh1378 ...

好，我研究研究，刚刚打比赛

柿子饼同学

zhangjinxuan 发表于 2022-10-23 12:16
好，我研究研究，刚刚打比赛

哈? 洛谷月赛?

zhangjinxuan

柿子饼同学 发表于 2022-10-23 12:39
哈? 洛谷月赛?

yes

柿子饼同学

zhangjinxuan 发表于 2022-10-23 12:41
yes

你做了多少题啊
我今天上午有课,  写了前两题 120 ...

zhangjinxuan

柿子饼同学 发表于 2022-10-23 12:47
你做了多少题啊
我今天上午有课,  写了前两题 120 ...

前两题190，总分210

zhangjinxuan

柿子饼同学 发表于 2022-10-23 12:47
你做了多少题啊
我今天上午有课,  写了前两题 120 ...

现在帮弟弟做作业，暂时不聊了