 6/23/2017 - 4:05 PM

## 77. Combinations

1. Combinations
``````class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
self.res = []
self.cur = []
self.backtracking(1,n,k)
return self.res
def backtracking(self, start,end, num):
# To select `num` elements from `start`(including) to `end`(including).
if (end-start)+1 < num:
# If there's not enough numbers.
return
if num == 0:
# If `num` is used up, append self.cur to self.res
self.res.append([each for each in self.cur])
return
for curNum in range(start, end+1):
# For every curNum from start to end (both including),
# append curNum to self.res and then backtracking from curNum+1 to end, for num-1 elements,
# delete curNum after it is done.
self.cur.append(curNum)
self.backtracking(curNum+1,end,num-1)
del self.cur[-1]
``````

https://leetcode.com/problems/combinations/#/description

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example, If n = 4 and k = 2, a solution is:

``````[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
``````