Daily LeetCode Challenge - 491. Non-decreasing Subsequences

Problem From.
https://leetcode.com/problems/non-decreasing-subsequences/

오늘 문제는 backtracking 알고리즘을 통해 풀수 있는 문제로 DFS 를 이용하여 풀었다.

각각의 경우에 대해 DFS 를 수행하면서 이미 그 답을 봤으면 다시 위로 올라가서 더 이상 탐색하지 않고 그 경우를 배제하는 식으로 수행시간을 줄여나갔다.

class Solution {
    
    val answer = arrayListOf<List<Int>>()
    
    fun findSubsequences(nums: IntArray): List<List<Int>> {
        
        nums.forEachIndexed { index, num ->
            val sub = arrayListOf<Int>()
            sub.add(num)
            DFS(sub, index, nums)
        }
        
        return answer.toList()
    }
    
    private fun DFS(sub: ArrayList<Int>, index: Int, nums: IntArray) {
        
        if(answer.contains(sub)) return
        if(sub.size >= 2) answer.add(sub.toList())
        
        for(i in index + 1 until nums.size) {
            if(nums[i] >= sub.last()) {
                sub.add(nums[i])
                DFS(sub, i, nums)
                sub.removeAt(sub.lastIndex)
            }
        }
        
    }
    
}