我们定义递归函数 backtrack(first, output) 表示从左往右填到第 \(\textit{first}\) 个位置，当前排列为 \(\textit{output}\)。 那么整个递归函数分为两个情况：
如果 \(\textit{first}==n\)，说明我们已经填完了 n 个位置（注意下标从 0 开始），找到了一个可行的解，我们将 \(\textit{output}\) 放入答案数组中，递归结束。
如果 \(\textit{first}<n\)，我们要考虑这第 \(\textit{first}\) 个位置我们要填哪个数。根据题目要求我们肯定不能填已经填过的数，因此很容易想到的一个处理手段是我们定义一个标记数组 \(\textit{vis}[]\) 来标记已经填过的数，那么在填第 \(\textit{first}\) 个数的时候我们遍历题目给定的 n 个数，如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数 backtrack(first + 1, output)。回溯的时候要撤销这一个位置填的数以及标记，并继续尝试其他没被标记过的数。
使用标记数组来处理填过的数是一个很直观的思路，但是可不可以去掉这个标记数组呢？毕竟标记数组也增加了我们算法的空间复杂度。
答案是可以的，我们可以将题目给定的 n 个数的数组 \(\textit{nums}\) 划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数，我们在回溯的时候只要动态维护这个数组即可。
具体来说，假设我们已经填到第 \(\textit{first}\) 个位置，那么 \(\textit{nums}\) 数组中 \([0,\textit{first}-1]\) 是已填过的数的集合，\([\textit{first},n-1]\) 是待填的数的集合。我们肯定是尝试用 \([\textit{first},n-1]\) 里的数去填第 \(\textit{first}\) 个数，假设待填的数的下标为 i ，那么填完以后我们将第 i 个数和第 \(\textit{first}\) 个数交换，即能使得在填第 \(\textit{first}+1\)个数的时候 \(\textit{nums}\) 数组的\([0,first]\) 部分为已填过的数，\([\textit{first}+1,n-1]\) 为待填的数，回溯的时候交换回来即能完成撤销操作。
举个简单的例子，假设我们有 [2, 5, 8, 9, 10] 这 5 个数要填入，已经填到第 3 个位置，已经填了 [8,9] 两个数，那么这个数组目前为 [8, 9 | 2, 5, 10] 这样的状态，分隔符区分了左右两个部分。假设这个位置我们要填 10 这个数，为了维护数组，我们将 2 和 10 交换，即能使得数组继续保持分隔符左边的数已经填过，右边的待填 [8, 9, 10 | 2, 5] 。
当然善于思考的读者肯定已经发现这样生成的全排列并不是按字典序存储在答案数组中的，如果题目要求按字典序输出，那么请还是用标记数组或者其他方法。
由于是不重复的全排列，所以我们采用交换法就可以了。
我们维护一个[1,2,3]数组，从第一个开始，交换到最后一个，两两交换。
方法：交换省去标志数组
一般我们使用这种方法来表示不断前进的选择，即 本次选择不会考虑左边之前的选择，从start右边开始选。
相当于我们使用start把数组划分为了两个部分，第一个部分就是我们已经选择好的元素，第二部分就是我们还未选择的元素，我们需要做的就是从start开始将还未选择的元素放入左边已选择的元素中(start + 1)。
好处：这样我们可以省去用于存储数组访问情况的used[]数组，因为我们已选择和未选择已经分开了。
即 以first为界限，first左边为排好序的元素，first右边为未排好序的元素，我们需要从右边挑选出元素放入左边。
无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
示例1:
输入：S = "qwe" 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]