class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
candidates=[x for x in range(1,n+1)]
if k>n:
return []
elif k==n:
return [candidates]
res=[]
line=[]
self.helper(candidates,k,res,line)
return res
def helper(self,candidates,k,res,line):
if len(line)==k:
res.append(x for x in line)
return
for i,x in enumerate(candidates):
line.append(x)
self.helper(candidates[i+1:],k,res,line)
line.pop()
"""
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
