[LeetCode] 077. Combinations *
-
date_range April 10, 2019 - Wednesday info
Problem (Medium)
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
Example:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Approach 1: (My Solution: BackTracking)
Idea
Typical backtracking intuition.
Solution
class Solution1:
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
res = []
self.backtrack(res, [], 0, n, k)
return res
def backtrack(self, res, item, lower, n, k):
if len(item) == k:
res.append(item)
return
for i in range(lower, n):
self.backtrack(res, item + [i+1], i+1, n, k)
Complexity
- Time: $O()$
- Space: $O()$
Approach 2: Backtracking Improved *
Idea
AC Python backtracking iterative solution 60ms
Solution
class Solution1:
def combine(self, n, k):
ans = []
stack = []
x = 1
while True:
l = len(stack)
if l == k:
ans.append(stack[:])
if l == k or x > n - k + l + 1:
if not stack:
return ans
x = stack.pop() + 1
else:
stack.append(x)
x += 1
# 26 / 26 test cases passed.
# Status: Accepted
# Runtime: 60 ms
# 98.51%
Complexity
- Time: $O()$
- Space: $O()$
KF