算法题--组合选取

image.png

0. 链接

题目链接

1. 题目

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

2. 思路1：回溯法

对于每个组合结果而言，每个元素可能出现在单个结果里，也可能不出现，所以需要逐个尝试。

按照回溯法的套路:

• 选择
• 深度迭代
• 撤销选择

可以从1-n遍历每个数字的情况，原则是不回头选取, 这样可以避免重复结果.

3. 代码

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        combs = list()
        comb = list()
        self.collect(combs, comb, 1, n, k)
        return combs

    def collect(self, combs: List[List[int]], comb: List[int], start: int, n: int, k: int):
        if k == 0:
            combs.append(comb.copy())
        else:
            for i in range(start, n + 1):
                comb.append(i)
                self.collect(combs, comb, i + 1, n, k - 1)
                comb.pop()


def my_test(solution: Solution, n: int, k: int):
    print('n={}, k={} => {}'.format(n, k, solution.combine(n, k)))


solution = Solution()
my_test(solution, 4, 2)
my_test(solution, 5, 2)
my_test(solution, 2, 1)

输出结果

n=4, k=2 => [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
n=5, k=2 => [[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]
n=2, k=1 => [[1], [2]]

4. 结果

image.png