问题描述
https://leetcode.com/problems/permutations-ii/
解决思路
大体思路和46题一样，只不过需要增加一个boolean数组来判断当前元素是否被用过了。((i > 0 && nums[i] == nums[i - 1])，这一句是在判重类型的题经常会用的模板。
代码
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
//corner case
if(nums.length == 0 || nums == null) return res;
Arrays.sort(nums);
//the boolean array used to record whether elements has been used or not
helper(res, new ArrayList<>(), nums, new boolean[nums.length]);
return res;
}
public void helper(List<List<Integer>> res, List<Integer> list, int[] nums, boolean[] used){
if(list.size() == nums.length){
res.add(new ArrayList(list));
return;
}
for(int i = 0; i < nums.length; i++){
//to judge whether element with index i has been used or not
if(used[i] || ((i > 0 && nums[i] == nums[i - 1]) && used[i - 1])) continue;
list.add(nums[i]);
used[i] = true;
helper(res, list, nums, used);
list.remove(list.size() - 1);
used[i] = false;
}
}
}
复杂度分析
- 时间复杂度：O(2^n)
- 空间复杂度：O(n)
