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

zhangjinxuan · 发表于 2022-10-23 10:43:44

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

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

#include <cstdio>
using namespace std;

int n, res[13]; 
bool u[13];

void dfs(int c) {
        if (c == n + 1) {
                for (int i = 1; i <= n; ++i) {
                        printf("%d ", res[i]);
                }
                puts("");
                return;
        }
        for (int i = 1; i <= n; ++i) {
                if (!u[i]) {
                        u[i] = 1;
                        res[c] = i;
                        dfs(c + 1);
                        u[i] = 0;
                }
        }
}

int main() {
        scanf("%d", &n);
        dfs(1);
}

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

最佳答案

月排行榜 / 总排行榜

柿子饼同学

2022-10-23 11:47:13

本帖最后由柿子饼同学于 2022-10-23 11:49 编辑

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

跳转到最佳答案楼层