Permutations, Subsets | LeetCode | Python3 🐍

 

📄 목차

 

 

 

백트레킹의 대표적인 문제인 permutation과 subset을 풀어보겠습니다.

🤔 문제1 : Permutations

문제: https://leetcode.com/problems/permutations/

주어진 리스트로 순서를 조합하여 만들 수 있는 모든 리스트을 만들어 반환하는 문제입니다. 

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ret = []
        def getPermutation(current_array, item_list):
            ret.append(current_array)
            if not item_list: return
            for idx in range(len(item_list)):
                getPermutation(current_array+[item_list[idx]], (item_list[idx+1:]))

        getPermutation([], nums)
        return ret

 

💡 풀이

1. Backtracking

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ret = []
        def getPermutation(current_array, item_list):
            if not item_list: ret.append(current_array)
            for idx in range(len(item_list)):
                getPermutation(current_array+[item_list[idx]], (item_list[:idx] if idx != 0 else [])+(item_list[idx+1:]))

        getPermutation([], nums)
        return ret

current_array 에는 현재까지 만든 리스트를, item_list에는 앞으로 리스트에 넣어야 할 아이템들을 전달합니다. 

 

내부에서 getPermutation을 계속 호출하는 구조이고, getPermutation 자체가 하나의 for loop을 갖고 있어서

전체 케이스에 대해서 다 한번씩 보기 때문에 시간복잡도는 O(n!)이겠네요

 

 

🤔 문제2 : Subsets

문제: https://leetcode.com/problems/subsets/

주어진 리스트의 모든 부분집합을 구하는 문제입니다.

접근방식은  Permutation과유사하지만 1. 순서를 고려하지 않고, 2. 리스트의 아이템이 n개가 아니어도 됩니다. 

 

 

💡 풀이

1. Permutations 기반의 풀이

처음에는 Permutations 문제에서 조금만 변형하면 될 것 같아서 아래와 같이 작성했습니다.

모든 아이템을 다 넣을 필요는 없으니 item_list에 이미 지나간 아이템은 포함하지 않습니다. 

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ret = []
        def getPermutation(current_array, item_list):
            ret.append(current_array)
            if not item_list: return
            for idx in range(len(item_list)):
                getPermutation(current_array+[item_list[idx]], (item_list[idx+1:]))

        getPermutation([], nums)
        return ret

 

2. One-liner 풀이

파이썬이라는 언어 특성 상 문제가 복잡해보여도 한줄짜리 풀이(?) 가 나오는 문제들이 있습니다. 

아래 풀이는 nums의 이이템을 돌면서 전체 배열에 추가해주는 방식입니다. 

예를들어 주어진 nums : [1,2,3] 이었다면

for 문을 돌 때 마다 아래와 같이 바뀌겠네요

[[]]

[[], [1]]

[[], [1], [2], [1, 2]]

[[], [1], [2], [1, 2], [3], [1,3], [2,3], [1,2,3]

새로 추가된 아이템을 볼드로 표시했는데, 보면 원래 있던 배열에 item값을 추가한 형태입니다.

 

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        if not nums: return [[]]
        ret = [[]]
        for item in nums: ret += [current + [item] for current in ret]
        return ret