给定一个整数数组 nums，返回给定数组中至少有两个元素的所有不同的可能非递减子序列。您可以按任何顺序返回答案。
示例1：
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6, 7,7],[7,7]]
示例2：
输入：nums = [4,4,3,2,1]
输出：[[4,4]]
限制：
1
-100
原始页面
public List<List<Integer>> findSubsequences(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> seq = new LinkedList<>();
Set<Integer> set = new HashSet<>();
backTracking(list, seq, nums, 0, set);
return list;
}
public void backTracking(List<List<Integer>>list, List<Integer> seq, int[] nums, int start, Set<Integer> set){
if(start == nums.length){
return;
}
for(int i=start; i<nums.length; i++){
// pruming the same elements
if(i!=start && set.contains(nums[i])){
continue;
}
if(seq.size() >= 1 && (nums[i] < seq.get(seq.size()-1))){
continue;
}
// the first element
set.add(nums[i]);
seq.add(nums[i]);
// evaluate non-decreasing
if(seq.size() > 1 && nums[i]>= seq.get(seq.size()-2)){
list.add(new ArrayList<>(seq));
}
if(seq.size() == 1 || nums[i]>= seq.get(seq.size()-1)){
backTracking(list,seq, nums, i+1, new HashSet<>());
}
// backTracking
seq.remove(seq.size()-1);
}
}
给定一个由不同整数组成的数组 nums，返回所有可能的排列。您可以按任意顺序返回答案。
示例1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]
示例2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
限制：
1
-10
nums 的所有整数都是唯一的。
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> permutation = new LinkedList<>();
Integer[] numsI = Arrays.stream(nums).boxed().toArray(Integer[]::new);
List<Integer> numList = new ArrayList(Arrays.asList(numsI));
backTracking(list, permutation, numList);
return list;
}
public void backTracking(List<List<Integer>> list, List<Integer> permutation, List<Integer> nums){
if(nums.size()==0){
list.add(new ArrayList<>(permutation));
return;
}
for(int i=0; i<nums.size(); i++){
permutation.add(nums.get(i));
List<Integer> workNums = new ArrayList<>(nums);
workNums.remove(Integer.valueOf(nums.get(i)));
backTracking(list, permutation, workNums);
permutation.remove(permutation.size()-1);
}
}
给定可能包含重复项的数字 nums 集合，以任何顺序返回所有可能的唯一排列。
示例1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]
限制：
1
-10
原始页面
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
List<Integer> permutation = new LinkedList<>();
int[] flags = new int[nums.length];
backTracking(permutation, nums, flags);
return list;
}
public void backTracking(List<Integer> permutation, int[] nums, int[] flags){
if(permutation.size() == nums.length){
list.add(new ArrayList<>(permutation));
return;
}
Set<Integer> set = new HashSet<>();
for(int i=0; i<nums.length; i++){
// flag work for recursion, set work for loop
if(flags[i] != 0 || set.contains(nums[i])){
continue;
}
int num = nums[i];
permutation.add(num);
set.add(num);
flags[i] = 1;
backTracking(permutation, nums, flags);
//recover to flag;
flags[i] = 0;
permutation.remove(permutation.size()-1);
}
}
以上是LeetCode DayBackTracking 第 4 部分的详细内容。更多信息请关注PHP中文网其他相关文章！
