排列，含重复元素和不重复元素两种情况的实现
用的典型的回溯法：
【排列，含重复元素和不重复元素两种情况的实现】
public List> permute(int[] nums) {
List> result = new ArrayList<>();
permute(result, nums, 0);
return result;
}private void permute(List> result, int[] nums, int idx) {
if (idx == nums.length) {
ArrayList arrayList = new ArrayList<>();
for (int num : nums) {
arrayList.add(num);
}
result.add(arrayList);
}
for (int i = idx;
i < nums.length;
i++) {
swap(nums, idx, i);
permute(result, nums, idx + 1);
swap(nums, idx, i);
}
}private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}public List> permuteUnique(int[] nums) {
List> result = new ArrayList<>();
permuteUnique(result, nums, 0);
return result;
}private void permuteUnique(List> result, int[] nums, int idx) {
if (idx == nums.length) {
ArrayList arrayList = new ArrayList<>();
for (int num : nums) {
arrayList.add(num);
}
result.add(arrayList);
}
for (int i = idx;
i < nums.length;
i++) {
if (!isDuplicate(nums, idx, i)) {
swap(nums, idx, i);
permuteUnique(result, nums, idx + 1);
swap(nums, idx, i);
}
}
}private boolean isDuplicate(int[] nums, int idx, int i) {
for (int i1 = idx;
i1 < i;
i1++) {
if (nums[i1] == nums[i]) {
return true;
}
}
return false;
} 推荐阅读
- 排序之冒泡和选择
- 《艾青诗选》读后感
- 【golang】leetcode初级-旋转数组&存在重复元素
- 分治|全排列算法整理
- 递归——数组全排列
- 全排列abc: a,b,c,ab,ac,bc,abc
- DFS|使用DFS（深搜）遍历所有的序列所有的子组合（子序列）（排列组合中的组合）
- 全排列（C语言）
- 集合的全排列（Java实现）
- 打印不重复的字符串全排列(递归)