Leetcode 491 - Increasing subsequences

Note:

  • This is a backtracking problem
  • To avoid duplicates but also preserve the order of original elements, you cannot just used sort on nums.
  • Use used[] to check duplicates on the same tree level before adding them to your path.
  • Need to add every qualified node instead of just leaf node.
    img

Given an integer array nums, return all the different possible increasing subsequences of the given array with at least two elements. You may return the answer in any order.

The given array may contain duplicates, and two equal integers should also be considered a special case of increasing sequence.

Example

1
2
Input: nums = [4,7,6,7]
Output: [[4,7], [4,6], [4,6,7], [7,7], [6,7], [4,7,7]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @param {number[]} nums
* @return {number[][]}
*/
var findSubsequences = function(nums) {
let ans = [];
let path = [];
backtracking(nums, 0);
return ans;

function backtracking(nums, startIndex) {
let used = [];
if (path.length > 1) {
ans.push([...path]);
}
for (let i = startIndex; i < nums.length; i++) {
if (path.length > 0 && nums[i] < path[path.length-1] || used.includes(nums[i])) continue;
used.push(nums[i]);
path.push(nums[i]);
backtracking(nums, i + 1);
path.pop();
}
}
};