北京
从零开始的第101天，我终于碰上了那道经典的“全排列”问题。
题目本身并不复杂：给你一个由不同整数组成的数组，你要返回它所有可能的排列顺序，答案可以按任意顺序给出。数字不能重复，每个元素只能用一次。
我看到测试用例的时候就在想，这不就是我们小时候排座位，换来换去总想找出所有坐法的那个游戏吗？比如 [1,2,3] 就能排出六种，[0,1] 三种，单个数字当然只剩一种。
我提交的第一版代码用的是典型的回溯写法：一个空路径开局，每次从原数组里挑一个还没放进路径的数字加进去，路径长度一达标就保存下来，然后不回头地退回上一步，继续试别的可能。它跑出了0毫秒，但我知道，这不是什么炫技，只是题目规模被限制在1到6个元素之间——排列的总量是阶乘级别的，一旦数据量起来，再笨的回溯也能让机器喘不过气来。
后来翻高赞解答，基本的回溯骨架几乎一样：递归结束条件、逐个检查当前元素是否已用、递归后弹出。唯一让人多看两眼的，是有人在注释里强调“我们需要将每个元素都锚定在每一个位置上，然后递归地生成未来索引的所有变体”。这句话我没跳过去，因为它解释了为什么要在每一层循环里跑遍整个数组，而不是下意识地去切分剩余部分。
还有一个用了set来标记访问状态的解法，耗时2毫秒，比我的多了一点，但它展现的是一种不同的记录视角——不是靠“路径里有没有”这种O(n)的查找，而是用一个额外集合存储用过哪些数字。在元素个数很少的时候，这种差异几乎可以忽略，但我还是把它存了下来，算作今天笔记里的一条备注。
熬到第101天，回溯题已经不是第一次遇到了，可每次写全排列，还是会先深吸一口气，仿佛不把“选择—递归—撤销”这三步刻进肌肉记忆，它就随时可能从指缝溜掉。
日子还长，挑战也还在继续。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
