全排列回溯经典-计算机考试—东方仙盟

一、题目描述

给定一个数组a[] = {1,2,3...n}，利用回溯算法输出数组的所有全排列。

例如 1 2 3 的全排列：123、132、213、231、312、321

算法思想：回溯、深度优先、标记已使用数字

二、完整代码

#include <stdio.h> // n: 总个数 // k: 当前正在选第k个数 int n = 3; // 保存当前排列结果 int res[10]; // 标记数字是否被用过 int used[10] = {0}; // 原始数组 int a[10] = {1,2,3}; // 回溯函数 void dfs(int k) { int i; // 【终止条件：软考超级高频填空】 if(k == n) { // 输出一组答案 for(i = 0; i < n; i++) { printf("%d", res[i]); } printf("\n"); return; } // 遍历所有数字，逐个尝试 for(i = 0; i < n; i++) { // 如果当前数字没被使用 if(!used[i]) { used[i] = 1; // 标记占用 res[k] = a[i]; // 放入当前位置 dfs(k + 1); // 递归填下一个位置 used[i] = 0; // 【回溯核心：撤销状态】 } } } int main() { dfs(0); return 0; }

三、逐句拆解（全部是填空考点）

1. 核心变量作用

• res[]：存放当前正在生成的一组排列

• used[]：标记哪个数字已经用过（防止重复选取）

• k：当前正在填充第k 位

2. 终止条件（必考空）

if(k == n)

所有位置全部填完，输出答案。和 N皇后row==N逻辑一模一样。

3. 回溯四步模板

1. 判断是否可用：!used[i]

2. 标记占用：used[i]=1

3. 递归深入：dfs(k+1)

4. 回溯撤销：used[i]=0 （最重要得分点）

四、和 N皇后 对比（你瞬间通了）

这两道是软考仅有的两大回溯原题模板

五、考场必背 3 个填空原话

1. 全排列算法属于回溯算法

2. 递归入口：dfs(0)

3. 回溯核心语句：used[i] = 0

六、极简通俗理解

逐个位置填数字，没用过就填上，继续填下一位；

一条路走到头得到一组解；

退回来、擦掉刚才填的数，换一个数继续试 =回溯。

人人皆为创造者，共创方能共成长

每个人都是使用者，也是创造者；是数字世界的消费者，更是价值的生产者与分享者。在智能时代的浪潮里，单打独斗的发展模式早已落幕，唯有开放连接、创意共创、利益共享，才能让个体价值汇聚成生态合力，让技术与创意双向奔赴，实现平台与伙伴的快速成长、共赢致远。

原创永久分成，共赴星辰大海

原创创意共创、永久收益分成，是东方仙盟始终坚守的核心理念。我们坚信，每一份原创智慧都值得被尊重与回馈，以永久分成锚定共创初心，让创意者长期享有价值红利，携手万千伙伴向着科技星辰大海笃定前行，拥抱硅基 生命与数字智能交融的未来，共筑跨越时代的数字文明共同体。

东方仙盟：拥抱知识开源，共筑数字新生态

在全球化与数字化浪潮中，东方仙盟始终秉持开放协作、知识共享的理念，积极拥抱开源技术与开放标准。我们相信，唯有打破技术壁垒、汇聚全球智慧，才能真正推动行业的可持续发展。

开源赋能中小商户：通过将前端异常检测、跨系统数据互联等核心能力开源化，东方仙盟为全球中小商户提供了低成本、高可靠的技术解决方案，让更多商家能够平等享受数字转型的红利。
共建行业标准：我们积极参与国际技术社区，与全球开发者、合作伙伴共同制定开放协议 与技术规范，推动跨境零售、文旅、餐饮等多业态的系统互联互通，构建更加公平、高效的数字生态。
知识普惠，共促发展：通过开源社区 、技术文档与培训体系，东方仙盟致力于将前沿技术转化为可落地的行业实践，赋能全球合作伙伴，共同培育创新人才，推动数字经济 的普惠式增长

阿雪技术观

在科技发展浪潮中，我们不妨积极投身技术共享。不满足于做受益者，更要主动担当贡献者 。无论是分享代码、撰写技术博客，还是参与开源项目 维护改进，每一个微小举动都可能蕴含推动技术进步的巨大能量。东方仙盟是汇聚力量的天地，我们携手在此探索硅基 生命，为科技进步添砖加瓦。

Hey folks, in this wild tech - driven world, why not dive headfirst into the whole tech - sharing scene? Don't just be the one reaping all the benefits; step up and be a contributor too. Whether you're tossing out your code snippets , hammering out some tech blogs, or getting your hands dirty with maintaining and sprucing up open - source projects, every little thing you do might just end up being a massive force that pushes tech forward. And guess what? The Eastern FairyAlliance is this awesome place where we all come together. We're gonna team up and explore the whole silicon - based life thing, and in the process, we'll be fueling the growth of technology