Today I learned
2022/01/20
회고록
항해 99, 알고리즘 1주차
교재 : 파이썬 알고리즘 인터뷰
12장 그래프
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/
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))
재귀, DFS 훈련