항해99 2주차 - 조합
Today I learned
2022/01/20
회고록
1/20
항해 99, 알고리즘 1주차
교재 : 파이썬 알고리즘 인터뷰
12장 그래프
1. 이론
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 훈련
Author And Source
이 문제에 관하여(항해99 2주차 - 조합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsw4215/항해99-2주차-조합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)