077.Combination.md

77.Combination

Question:

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],
]

Analysis:

回溯法或者迭代法或者递归法!

Solution:

class Solution(object):
    def backTracking(self,l,k,index,tl,rl):
        if len(tl)==k:
            rl.append(tl)
            return True
        while len(l)-index>=k-len(tl): 
            sl=tl+[l[index]]
            index+=1
            self.backTracking(l,k,index,sl,rl)
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        l = list(range(1,n+1))
        rl = []
        self.backTracking(l,k,0,[],rl)
        return rl