(nums,i+1);
temp.remove(temp.size() - 1);
}
}
}
90、子集 II
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
subsetsWithDupHandler(nums, 0);
return result;
}
public void subsetsWithDupHandler(int[] nums, int index){
if(index == nums.length){
result.add(new ArrayList<>(temp));
return;
}
result.add(new ArrayList<>(temp));
for(int i = index; i < nums.length; i++){
// 不能 包含重复的子集
if(i > 0 &&i > index && nums[i] == nums[i - 1]){
continue;
}
temp.add(nums[i]);
subsetsWithDupHandler(nums, i + 1);
temp.remove(temp.size() - 1);
}
}
}
491、递增子序列
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> findSubsequences(int[] nums) {
// 递增子序列中 至少有两个元素
findSubsequencesHandler(nums, 0);
return result;
}
public void findSubsequencesHandler(int[] nums, int index){
if(temp.size() > 1){
result.add(new ArrayList<>(temp));
}
int[] used = new int[201];
for(int i = index; i < nums.length; i++){
if(temp.size() != 0 && nums[i] < temp.get(temp.size() - 1) || (used[nums[i] + 100] == 1)){
continue;
}
used[nums[i] + 100] = 1;
temp.add(nums[i]);
findSubsequencesHandler(nums, i + 1);
temp.remove(temp.size() - 1);
}
}
}
46、全排列
class Solution {
public List<List<Integer>> result = new ArrayList<>();
public List<Integer> temp = new ArrayList<>();
public int[] used;
public List<List<Integer>> permute(int[] nums) {
used = new int[nums.length];
find(nums);
return result;
}
public void find(int[] nums){
if(temp.size() == nums.length){
result.add(new ArrayList<Integer>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
if(used[i] == 1){
continue;
}
temp.add(nums[i]);
used[i] = 1;
find(nums);
temp.remove(temp.size()-1);
used[i] = 0;
}
}
}
47、全排列 II
class Solution {
public List<List<Integer>> result = new ArrayList<>();
public List<Integer> temp = new ArrayList<>();
public int[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
used = new int[nums.length];
Arrays.sort(nums);
find(nums);
return result;
}
public void find(int[] nums){
if(temp.size() == nums.length){
result.add(new ArrayList<Integer>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
if(used[i] == 1){
continue;
}
if(i > 0 && nums[i] == nums[i - 1] && used[i-1] != 1){
continue;
}
temp.add(nums[i]);
used[i] = 1;
find(nums);
temp.remove(temp.size()-1);
used[i] = 0;
}
}
}
332、重新安排行程
//基本参考代码随想录
class Solution {
public LinkedList<String> result;
public LinkedList<String> path = new LinkedList<String>();
public List<String> findItinerary(List<List<String>> tickets) {
Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1)));//字典排序
path.add("JFK");
int[] used = new int[tickets.size()];
findItineraryHanlder(tickets, used);
return result;
}
pub