leetcode47. 全排列 II
II 排列
2023-09-27 14:25:55 时间
难度中等223
给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
思路:和全排列差不多,要排序+剪枝,懒得写了给个题解网址。
class Solution {
int[] visited;//标记数组
List<List<Integer>> res = new ArrayList<>();//答案
public List<List<Integer>> permuteUnique(int[] nums) {
//修改1:排序
Arrays.sort(nums);
visited = new int[nums.length];
backtrack(nums, new ArrayList<Integer>());
return res;
}
private void backtrack(int[] nums, ArrayList<Integer> tmp) {
if (tmp.size() == nums.length) {
res.add(new ArrayList<>(tmp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i] == 1) continue;
//修改2:剪枝,
if (i > 0 && nums[i - 1] == nums[i] && visited[i - 1]==0) {
continue;
}
visited[i] = 1;
tmp.add(nums[i]);
backtrack(nums, tmp);
visited[i] = 0;
tmp.remove(tmp.size() - 1);
}
}
}
相关文章
- Lintcode: Sort Colors II
- BZOJ3569 : DZY Loves Chinese II
- NYOJ 469 擅长排列的小明 II
- HDU 1207 汉诺塔II (简单DP)
- 力扣解法汇总219-存在重复元素 II
- [LintCode] Intersection of Two Arrays II 两个数组相交之二
- [LeetCode] 267. Palindrome Permutation II 回文全排列之二
- [LeetCode] 244. Shortest Word Distance II 最短单词距离之二
- 940. Distinct Subsequences II
- 552. Student Attendance Record II
- 140. Word Break II