[LeetCode] 491. Non-decreasing Subsequences

😎풀이

1. 방문 기록을 저장할 Set객체 선언
2. 첫번째 요소부터 백트레킹 수행
   2-1. 현재 인덱스부터, 이후 요소 중 오름차 순으로 정렬될 수 있는 서브시퀀스 탐색
   2-2. 서브시퀀스의 길이가 2 이상이며, 고유한 경우 정답 배열에 추가
3. 고유한 오름차 순 서브시퀀스 중 길이가 2 이상인 배열 반환

function findSubsequences(nums: number[]): number[][] {
    const n = nums.length
    const result = []
    const visited = new Set<string>()
    function backTracking(idx: number, arr: number[]) {
        if(idx === n) return
        const last = arr[arr.length - 1]
        for(let i = idx; i < n; i++) {
            if(nums[i] < last) continue
            const nextArr = [...arr, nums[i]]
            const nextKey = String(nextArr)
            if(visited.has(nextKey)) continue
            visited.add(nextKey)
            if(nextArr.length >= 2) result.push(nextArr)
            backTracking(i + 1, nextArr)
        }
    }
    backTracking(0, [])
    return result
};