depth first search, recursive function
class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
result=[]
self.combineRecur(n,result,0,[],k)
return result
def combineRecur(self,n,result,start,out,k):
if k==0:
result.append(out[:])
return
for i in xrange(start,n):
out.append(i+1)
self.combineRecur(n,result,i+1,out,k-1)
out.pop()
if (k-len(out))>n-i:
return
from itertools import combinations
class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
return list(combinations(range(1,n+1),k))
using list comprehension
class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
if k == 0:
return [[]]
return [[i]+rest for i in range(1,n+1) for rest in self.combine(i-1,k-1)]
