491. Non-decreasing Subsequences java solution with Backtracking
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.
Input: nums = [4,6,7,7]
Output:7
Explanation: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
491. Non-decreasing Subsequences java solution with Approach 1:Backtracking
class Solution {
public List<List<Integer>> findSubsequences(int[] nums) {
Set<List<Integer>> answer = new HashSet<>();
List<Integer> single_sequence = new ArrayList<>();
backtrackFun(nums, 0, single_sequence, answer);
return new ArrayList(answer);
}
void backtrackFun(int[] nums, int index, List<Integer> single_sequence , Set<List<Integer>> answer){
if(index == nums.length){ //index at last element
if(single_sequence.size() >= 2){
answer.add(new ArrayList<>(single_sequence));
}
return;
}
//append element if its in increasing order
//nums[] = [4,6,7,7]
//output =[[4,6],[4,6,7]]
//sequences =>[4,6,7], [4,6,7,7]
if(single_sequence.isEmpty() || single_sequence.get(single_sequence.size() - 1) <= nums[index]){
single_sequence.add(nums[index]); // if the element is greater than or equal to the last element of sequence
backtrackFun(nums, index + 1, single_sequence, answer);
single_sequence.remove(single_sequence.size() - 1);
}
backtrackFun(nums, index + 1, single_sequence, answer);
}
}
491. Non-decreasing Subsequences java solution with Approach 2: Bitmasks
class Solution {
public List<List<Integer>> findSubsequences(int[] nums) {
int n = nums.length;
int m = 1<<n;
Set<List<Integer>> answer = new HashSet<>();
for(int bitmask = 1; bitmask<m; bitmask++){
List<Integer> seq = new ArrayList<>();
for(int i = 0; i< n; i++){
int p = bitmask >> i ;
int q = p & 1;
if(q == 1){
seq.add(nums[i]);
}
}
if(seq.size() >= 2){
boolean isIncreasingFlag = true;
for(int i = 0; i< seq.size() - 1; i++){
isIncreasingFlag &= seq.get(i) <= seq.get(i + 1);
}
if(isIncreasingFlag) {
answer.add(seq);
}
}
}
return new ArrayList<>(answer);
}
}
