491. Non-decreasing Subsequences
Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.
Example 1:
Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
Example 2:
Input: nums = [4,4,3,2,1]
Output: [[4,4]]
Constraints:
1 <= nums.length <= 15
-100 <= nums[i] <= 100
Original Page
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);
}
}
46. Permutations
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
Constraints:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.
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);
}
}
47. Permutations II
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
Example 2:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
1 <= nums.length <= 8
-10 <= nums[i] <= 10
Original Page
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);
}
}
Top comments (0)