leetcode77 -- Combinations

leetcode77 -- Combinations

题目

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

这个题的意思就是要返回所有的C(n,k)的组合,首先想到的就是数学的办法,即利用组合数公式

C(n,k)=C(n-1,k-1)+C(n-1,k).

就是说看最后一个人有没有被选上,如果选上了,相当于从前面的n-1个选k-1个,如果没选上,相当于从前面的n-1个选k个。

所以把这两部分的都算上的话就是最终的结果了。


class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        if k>n or k<0:
            return []
        if k==0:
            return [[]]
        
        res = self.combine(n-1, k-1)
        for a in res:
            a.append(n)
            
        for a in self.combine(n-1,k):
            res.append(a)
            
        return res
        

感觉用递归解决这一类的问题真是太方便了,而且容易懂,递归真是太奇妙了!

大致的思路是先算出C(n-1,k-1)即从前面的n-1个取k-1个的情况,然后再把n放到里面去,然后另外一种情况就是C(n-1,k),两个合并到一块儿就是最终的结果。

不过这一类的题还有一种思路就是DFS,如下


class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        self.helper(n,k,1,[],res)
        return res  
    
    def helper(self, n,k, level, out, res):
        if len(out)==k:
            res.append(out[:])
            
        for i in range(level, n+1):
            out.append(i)   # 用这个
            
            self.helper(n,k, i+1, out, res)   # 往更深的地方走
             
            del(out[-1])    # 把这个删了,遍历其他的。
            
        return 

但是这里并没有用标记,因为这里得么的并不是全排列。这个题刚好和全排列那个题是对应的,那里要用标记,而这里不需要就可以了。因为这里顺序不同相当于是同一个。

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦