77-Combinations.py

'''Leetcode- https://leetcode.com/problems/combinations/'''
'''
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],
]
'''
defcombine(n, k):
result= []

defbacktrack(start,comb):
iflen(comb) ==k:
result.append(comb.copy())
return

foriinrange(start,n+1):
comb.append(i)
backtrack(i+1,comb)
comb.pop()

backtrack(1,[])
returnresult

#T: O(k.n^k)
#T: O(k. n!/(n-k)!k!)
#S: O(n)