Python Algorithm Q35

November 22, 2022

Q35 Combinations

Q

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Sample Input

Example 1

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2

Input: n = 1, k = 1 Output: [[1]] Explanation: There is 1 choose 1 = 1 total combination.

Constraints

1 <= n <= 20
1 <= k <= n

1. My Own Solution

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        pool = [i for i in range(1, n+1)]
        ans :List[List[int]] = []

        def dfs(startindex: int, currentlist: List):
            tmpcurrentlist = currentlist[:]
            
            if(len(currentlist) == k):
                ans.append(currentlist)
                return

            for i in range(startindex, len(pool)):
                dfs(i+1, tmpcurrentlist + [pool[i]])


        dfs(0, [])
        # print(ans)
        return ans
        
# test set
a = Solution()
a.combine(4, 2)

이전에 33번 문제 풀 때 기억을 살려서 먼저 append-return 조건부터 만들어놓고, 아래 for문에서 element가 중복되지 않게 넣으려면 index를 하나씩 뒤로 밀어서 for문으로 반복하면 되지 않을까 싶어서 했는데 1트만에 바로 됐다… 천잰가? 결과 자체만 놓고 보면 다른 코드와 비교해봤을 때 시간이 좀 많이 걸리긴 했다. 하지만 내 스스로, 그것도 1트만에 바로 accepted 받았다는 점에서 이미 감격…

2. My Own Solution #2

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []

        def dfs(startindex: int, currentlist: List):
            if(len(currentlist) == k):
                ans.append(currentlist)
                return 

            for i in range(startindex, n):
                dfs(i+1, currentlist + [i+1])

        dfs(0, [])
        # print(ans)
        return ans

원래 한 번에 통과하고 넘어간 걸로 만족하려고 했는데 다른 예시 풀이보니까 나랑 다른게 없는데 왜 이렇게 차이가 많이날까 고민하다가 조금 뜯어고친 코드이다. 유일하게 달라진 점은 원래 코드에서는 다음 재귀로 넘어갈 때 list가 mutate 되지 않도록 tmpcurrentlist를 만들었었는데, 생각해보니 변형될만한 부분이 아무데도 없어서 그냥 지워버렸다. 아마 매번 재귀할때마다 복사하고 시작해서 시간을 좀 잡아먹지 않았나 싶다. 근데 그보다 한 10번 돌렸는데 속도가 상위 12%에서 60%까지 왤케 변동이 컸을까… 이건 잘 모르겠다. 여기서 하나 더 깨달은 점은 내 첫번째 풀이도 그렇게 나쁜 코드는 아니었다는 것이다 ㅎㅎ 뭔가 구조적으로 확 바뀌어야 속도 빨라지는 줄 알았는데 그건 아니더라.

3. Given Solution #1

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        results = []

        def dfs(elements, start: int, k: int):
            if k == 0:
                results.append(elements[:])
                return
            
            for i in range(start, n+1):
                elements.append(i)
                dfs(elements, i+1, k-1)
                elements.pop()

        dfs([], 1, k)
        return results

책에 나온 풀이. 저번에 permutations 문제와 동일하게 재귀를 시작하는 시점을 영리하게 잘 잡아서 append한 상태로 보내고, 재귀 탈출하자마자 다시 pop시켜서 이후의 재귀에는 영향을 미치지 않도록 잘 설계한 풀이이다.

3. Given Solution #2

class Solution:
    def combine(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.combinations(range(1, n+1), k))

저번 permutation 문제에서도 썼던 라이브러리. 설명 생략.

Overall Review

DFS를 배우기 전에는 참 막막했을 문제들이 알고리즘에 대해 배우면서 조금씩 풀리는게 쏠쏠한 재미를 주는 것 같다. 반복해서 풀다 보니까 안보이던 것도 보이게 되는 것 같기도 하고 말이다. 나중에는 어떤 알고리즘이 나올지 기대되기도 하고 재밌을 것 같다.

Hyuntae H