Combinations

题目

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

思路分析

首先看到‘return all possible...’就会马上想到是不是DFS，然后分析题目发现要穷举所有n以内的所有的数字才能得到答案，就可以确定这道题的解法就是DFS。然后就是带入DFS的template实现。

本题有两种实现方式，一种是加法，当每个path的长度==k时，把这个path放到结果中；另外一种是减法，当path长度增加1时，k减去1，当k减到0时说明path的长度是k了，这时把path放入结果中

加法实现

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        if n < k: return []
        if n == k: return [range(1, n+1)]
        def dfs(n, k, startIndex, path, result):
            if len(path) == k: result.append(path)
            for i in range(startIndex, n+1):
                dfs(n, k, i+1, path+[i], result)
        result = []
        dfs(n, k, 1, [], result)
        return result

减法实现

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        if n < k: return []
        if n == k: return [range(1, n+1)]
        def dfs(n, k, startIndex, path, result):
            if k == 0: result.append(path)
            for i in range(startIndex, n+1):
                dfs(n, k-1, i+1, path+[i], result)
        result = []
        dfs(n, k, 1, [], result)
        return result