Leetcode: Combinations

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



Similar Problems:


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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/combinations
## Basic Ideas:
##          Get an array of n element, either 0 or 1
## Complexity: Time (Permutation), Space ?
class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        l = self.getCombine(n, k)
        res = []
        for combine in l:
            item = []
            for digit in xrange(n):
                if combine[digit] == 1:
                    item.append(digit + 1)
            if len(item) != 0:
                res.append(item)
        return res

    def getCombine(self, n, k):
        if n == k:
            return [[1]*n]
        if k > n or n == 0:
            return []
        if k == 0:
            return [[0]*n]
        res = []
        res_0 = self.getCombine(n-1, k)
        res_1 = self.getCombine(n-1, k-1)
        if len(res_0) != 0:
            for item in res_0:
                res.append([0] + item)

        if len(res_1) != 0:
            for item in res_1:
                res.append([1] + item)
        return res

# s = Solution()
# print s.combine(4, 2)
# print s.combine(1, 1)
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.