Description
Given a list of numbers, return all possible permutations.
You can assume that there is no duplicate numbers in the list.
Example
Example 1:
Input: [1]
Output:
[
[1]
]
Example 2:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Challenge
Do it without recursion.
思路：
具体思路参考下图，不断的往下寻找再往上回溯，另外注意此题不需要排序
还有一种非递归的写法，参考next permutation，非递归的全排列，采用的是迭代方式，在如何求下一个排列中，我们讲过如何求下一个排列，那么我们只需要不断调用这个nextPermutation方法即可。
一些可以做得更细致的地方：
为了确定何时结束，建议在迭代前，先对输入nums数组进行升序排序，迭代到降序时，就都找完了。有心的同学可能还记得在nextPermutation当中，当且仅当数组完全降序，那么从右往左遍历的指针i最终会指向0。所以可以为nextPermutation带上布尔返回值，当i为0时，返回false，表示找完了。要注意，排序操作在这样一个NP问题中，消耗的时间几乎可以忽略。
当数组长度为1时，nextPermutation会直接返回false；当数组长度为0时，nextPermutation中i会成为-1，所以返回false的条件可以再加上i为-1。
代码：
网友评论