46. Permutations
原题如下:
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
题目要求列出给定的不重复数字的所有排列结果。解题方法有两种。下面分别讲述。
方法一
第一种方法每次取一个数字,将数字插入现有的排列中形成新的排列,然后重复上面的过程直到所有数字都被取完。
实现代码如下:
1 | class Solution(object): |
方法二
第二种方法采用回溯法。将当前数字与后面的数字逐一交换,当与某一数字交换后,然后移动到下一个数字重复上面的操作。实现具体代码如下
1 | class Solution(object): |
47. Permutations II
原题如下:
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
这道题目的要求与上一道一样,只是在上面的基础上添加了存在重复数字的约束条件。
上面提到回溯法在这里不适用了(即使判定交换的元素是否相等),比如说对于[1,2,3,3]就不正确了。
采用方法一的直接插入法,从后往前插,遇到与当前要插入数字相同的数字时就终止当前排列的插入,进行下一个排列的插入。实现的具体代码如下:
1 | class Solution(object): |