Leetcode 491. Non-decreasing Subsequence with Python

문제

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: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

제한

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100

풀이법

1. 더럽게 느린 내 방법

from copy import deepcopy as dc

ans = list()

def search(nums: List[int], acc: List[int], n: int):
    global ans
    if n >= len(nums): return 
    if len(acc) == 0 or acc[len(acc)-1] <= nums[n]: 
        acc.append(nums[n])
    if len(acc) > 1 and acc not in ans:
        ans.append(dc(acc))
    for i in range(n+1, len(nums)):
        search(nums, dc(acc), i)

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        global ans
        ans = []
        for i in range(len(nums)):
            search(nums, [], i)
        return ans       
        

모든 가능한 방법을 다 찾아나가는데, 찾아나가는 방법이 무조건

숫자가 커지거나 같아지는 방법만 찾는다.

2. 백트래킹

일단 코드를 먼저 적고 뜯어보면서 이야기 하겠다.

from copy import deepcopy as cp

from copy import deepcopy as cp

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        ans = []
        p = []
        # 백트래킹 함수
        def backtrack(numbers: List[int], i: int):
            # 길이가 1보다 크면 기록에 남긴다.
            if len(p) > 1:
                ans.append(cp(p))

            # 숫자 이어나감
            for j in range(i, len(numbers)):
                # 비어있거나 숫자가 줄어들면 X
                if p and p[-1] > numbers[j]: continue

                if j > i and numbers[j] in numbers[i:j]: continue

                # 백트래킹 추가 -> recursive -> 빼기
                p.append(nums[j])
                backtrack(numbers, j+1)
                p.pop()
        backtrack(nums, 0)
        print(ans)
        return ans

백트래킹을 이용한다.