LeetCode 491: Non-decreasing Subsequences
Problem Description
Explanation
To solve this problem, we can use backtracking to generate all possible non-decreasing subsequences of the given array. At each step, we have two choices: either include the current element in the subsequence or skip it. We recursively explore both choices to generate all possible subsequences that satisfy the non-decreasing condition. To avoid duplicates, we use a set to store the subsequences. Finally, we convert the set to a list and return the result.
- Time complexity: O(2^N) where N is the number of elements in the input array.
- Space complexity: O(2^N) for the output list of subsequences.
Solutions
import java.util.*;
class Solution {
public List<List<Integer>> findSubsequences(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
List<Integer> temp = new ArrayList<>();
backtrack(nums, 0, temp, result);
return new ArrayList<>(result);
}
private void backtrack(int[] nums, int index, List<Integer> temp, Set<List<Integer>> result) {
if (temp.size() >= 2) {
result.add(new ArrayList<>(temp));
}
if (index == nums.length) {
return;
}
for (int i = index; i < nums.length; i++) {
if (temp.isEmpty() || nums[i] >= temp.get(temp.size() - 1)) {
temp.add(nums[i]);
backtrack(nums, i + 1, temp, result);
temp.remove(temp.size() - 1);
}
}
}
}Related LeetCode Problems
Loading editor...