题目主要信息:
- 给定一组可能有重复数字的数组，输出该数组的全部排列
- 输出结果按照字典序升序排列
举一反三：
学习完本题的思路你可以解决如下题目：
递归+回溯（推荐使用）
知识点：递归与回溯
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。
思路：
这道题类似没有重复项数字的全排列，但是因为交换位置可能会出现相同数字交换的情况，出现的结果需要去重，因此不便于使用交换位置的方法。
我们就使用临时数组去组装一个排列的情况：每当我们选取一个数组元素以后，就确定了其位置，相当于对数组中剩下的元素进行全排列添加在该元素后面，给剩余部分进行全排列就是一个子问题，因此可以使用递归。
- 终止条件： 临时数组中选取了n个元素，已经形成了一种排列情况了，可以将其加入输出数组中。
- 返回值： 每一层给上一层返回的就是本层级在临时数组中添加的元素，递归到末尾的时候就能添加全部元素。
- 本级任务： 每一级都需要选择一个不重复元素加入到临时数组末尾（遍历数组选择）。
回溯的思想也与没有重复项数字的全排列类似，对于数组[1,2,2,3]，如果事先在临时数组中加入了1，后续子问题只能是[2,2,3]的全排列接在1后面，对于2开头的分支达不到，因此也需要回溯：将临时数组刚刚加入的数字pop掉，同时vis修改为没有加入，这样才能正常进入别的分支。
//标记为使用过
vis[i] = true;
//加入数组
temp.add(num[i]);
recursion(res, num, temp, vis);
//回溯
vis[i] = false;
temp.remove(temp.size() - 1);
具体做法：
- step 1：先对数组按照字典序排序，获取第一个排列情况。
- step 2：准备一个数组暂存递归过程中组装的排列情况。使用额外的vis数组用于记录哪些位置的数字被加入了。
- step 3：每次递归从头遍历数组，获取数字加入：首先根据vis数组，已经加入的元素不能再次加入了；同时，如果当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用，也不需要将其纳入。
- step 4：进入下一层递归前将vis数组当前位置标记为使用过。
- step 5：回溯的时候需要修改vis数组当前位置标记，同时去掉刚刚加入数组的元素，
- step 6：临时数组长度到达原数组长度就是一种排列情况。
图示：
Java实现代码：
import java.util.*;
public class Solution {
public void recursion(ArrayList<ArrayList<Integer>> res, int[] num, ArrayList<Integer> temp, Boolean[] vis){
//临时数组满了加入输出
if(temp.size() == num.length){
res.add(new ArrayList<Integer>(temp));
return;
}
//遍历所有元素选取一个加入
for(int i = 0; i < num.length; i++){
//如果该元素已经被加入了则不需要再加入了
if(vis[i])
continue;
if(i > 0 && num[i - 1] == num[i] && !vis[i - 1])
//当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了
continue;
//标记为使用过
vis[i] = true;
//加入数组
temp.add(num[i]);
recursion(res, num, temp, vis);
//回溯
vis[i] = false;
temp.remove(temp.size() - 1);
}
}
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
//先按字典序排序
Arrays.sort(num);
Boolean[] vis = new Boolean[num.length];
Arrays.fill(vis, false);
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> temp = new ArrayList<Integer>();
recursion(res, num, temp, vis);
return res;
}
}
C++实现代码：
class Solution {
public:
void recursion(vector<vector<int> > &res, vector<int> &num, vector<int> &temp, vector<int> &vis){
//临时数组满了加入输出
if(temp.size() == num.size()){
res.push_back(temp);
return;
}
//遍历所有元素选取一个加入
for(int i = 0; i < num.size(); i++){
//如果该元素已经被加入了则不需要再加入了
if(vis[i])
continue;
if(i > 0 && num[i - 1] == num[i] && !vis[i - 1])
//当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了
continue;
//标记为使用过
vis[i] = 1;
//加入数组
temp.push_back(num[i]);
recursion(res, num, temp, vis);
//回溯
vis[i] = 0;
temp.pop_back();
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
//先按字典序排序
sort(num.begin(), num.end());
//标记每个位置的元素是否被使用过
vector<int> vis(num.size(), 0);
vector<vector<int> > res;
vector<int> temp;
//递归获取
recursion(res, num, temp, vis);
return res;
}
};
Python实现代码：
class Solution:
def recursion(self, res:List[List[int]], num:List[int], temp:List[int], vis:List[int]):
#临时数组满了加入输出
if len(temp) == len(num):
res.append(temp.copy())
return
#遍历所有元素选取一个加入
for i in range(len(num)):
#如果该元素已经被加入了则不需要再加入了
if vis[i]==1:
continue
if i > 0 and num[i - 1] == num[i] and not vis[i - 1]:
#当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了
continue
#标记为使用过
vis[i] = 1
#加入数组
temp.append(num[i])
self.recursion(res, num, temp, vis)
#回溯
vis[i] = 0
temp.pop()
def permuteUnique(self , num: List[int]) -> List[List[int]]:
#先按字典序排序
num.sort()
#标记每个位置的元素是否被使用过
vis = [0]*len(num)
res = list(list())
temp = list()
# 递归获取
self.recursion(res, num, temp, vis)
return res
复杂度分析：
- 时间复杂度：，全排列的全部情况为n!，每次递归过程都是遍历数组查找元素，这里是
- 空间复杂度：，递归栈的最大深度为数组长度n，临时数组temp的空间也为，res属于返回必要空间
京公网安备 11010502036488号