항해99 2주차 - 조합

Today I learned
2022/01/20

회고록

1/20

항해 99, 알고리즘 1주차

교재 : 파이썬 알고리즘 인터뷰

12장 그래프

1. 이론

https://velog.io/@jsw4215/%ED%95%AD%ED%95%B499-2%EC%A3%BC%EC%B0%A8-%EA%B7%B8%EB%9E%98%ED%94%84DFSBFS-%EC%9D%B4%EB%A1%A0-%EC%A0%95%EB%A6%AC

2. 문제

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

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:

Input: n = 1, k = 1
Output: [[1]]

Constraints:

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

https://leetcode.com/problems/combinations/

3. MySol

• Recursive DFS

def solution(n, k):

    result = []

    nList = []

    curr_node = []
    next_node = []

    for i in range(1,n+1):
        nList.append(i)


    def dfsFunction(nList, k, index):
        k-=1
        if k<0:
            result.append(curr_node[:])
            return

        for i in range(index, len(nList)):
            next_node = nList[:]
            next_node.remove(nList[i])

            curr_node.append(nList[i])
            dfsFunction(next_node, k, index+1)
            curr_node.pop()

    dfsFunction(nList, k, 0)

    return result

if __name__ == '__main__':

    n = 4
    k = 2

    result = solution(n, k)

    print('result : ' + str(result))

4. 배운 점

• 순열 코드를 이해한 후, 해당 부분을 응용하여 조합 문제를 풀었다.
• 도움이 많이 되는 문제

5. 총평

재귀, DFS 훈련