输出1-n的全排列(按字典序)

先上题

再上代码

这个问题的棘手之处就在于n是不确定的。

如果n确定，为了按照字典序输出，我们可以通过循环的嵌套以及几个条件判断直接输出，比如这样：

但n是不确定的，我们并不知道要套几层循环，这就需要递归的使用。

递归的核心有三点：起始点、递推关系和边界条件。

在这个问题里，起始点可以从第一位开始。

而递推关系体现为：我们如果有了这个数选取个数后在前位上所有的排列，我们可以在它的基础上给出这个数在前位上所有选取后的排列。

对于每一种已知的排列，我们只需要从到遍历一遍，分别找到所有在这一个排列中没有出现过的数字，放在第位上，便可以得到需要的结果。

而边界条件就是，也即当我们把前位都填充完之后，我们已经得到了一种排列，只需要输出即可。

到这里这个递归的思路已经了然了，剩下的是一个小的优化，也就是数组的加入。

在我们从到遍历的时候，需要与前面的数比对以确定是否重复，这是一笔不小的开销。为了减少这个开销，我们选择开一个sgn数组，用于标志该数是否已在前位中被选取。

当我们在第位上放置一个数时，我们将置为，表示该数已被选取，而当后面的函数，即调用结束时，我们将置为，因为无论之后是还在该层继续循环，还是跳出循环，该位都不再选取。

把两个代码作比较可能会好理解一些：

中的循环就对应中的循环，只不过中循环的嵌套是直接写出来的，中的循环嵌套则通过递归实现。中取不同变量名是为了区分，而中不同层的循环在不同的函数中，不需要在名字上做区分。

中的条件判断就对应中对的判断以及反复的置置。

中最后一次循环正常结束便可输出一个结果，而中则是到第时，递归到最底层，输出结果。不同点则在于的循环中完整保留了各位的信息，而需要一个数组来存放这些信息。

以上。

递归还是要多写，刚接触的时候确实会比较懵，但把三个核心点写好，递归还是可以以简单的思路实现的。