Title: Combinations Source: leetcode.com
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:
|
1 2 3 4 5 6 7 8 |
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] |
Python solution (a)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
''' https://leetcode.com/problems/combinations/ ''' class Solution(object): def __init__(self): self.res = [] def helper(self, cur_set, k, low, high): if len(cur_set) == k: self.res.append(cur_set) return else: for i in range(low, high + 1): self.helper(cur_set + [i], k, i + 1, high) def combine(self, n, k): """ :type n: int :type k: int :rtype: List[List[int]] """ if k == 0: return self.res self.helper([], k, 1, n) return self.res |
Python solution (b)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
''' https://leetcode.com/problems/combinations/ ''' class Solution(object): def __init__(self): self.res = [] def helper(self, cur_set, k, rem): if len(cur_set) == k: self.res.append(cur_set) return else: for i in range(0, len(rem)): self.helper(cur_set + [rem[i]], k, rem[i+1:]) def combine(self, n, k): """ :type n: int :type k: int :rtype: List[List[int]] """ if k == 0: return self.res rem = range(1,n+1) self.helper([], k, rem) return self.res |