一.引言
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4 k = 2
输出: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
n=4 代表待组合 list = [1,2,3,4]
二.递归调用
1.方法参数
combine 为主方法，getCombine 为实际递归调用的方法，主要有5个参数：
res[list] : 保存存储结果
prefix[lsit] : 保存当前前缀
n : 给定数字，代表1-n的数字范围
k : 代表组合的个数
start : 标识当前起始位置
2.方法思路
采用递归的方式遍历
(1) 从1开始固定位置作为前缀，随后遍历1之后的元素并添加到前缀中
(2) 当 k = 0 时代表此时前缀的长度已达到预定长度 k，此时将 prefix 添加到 result
(3) 随后执行 pop 操作，删掉前缀最后一位并将start 加1，相当于固定另外一个数字继续遍历
(4) 当 start 大于 n 时代表遍历完全部数组元素，
class Solution(object):def combine(self, n, k):res = []self.get_combine(res, [], n, k, 1)return resdef get_combine(self, res, prefix, n, k, start):if k == 0:res.append(list(prefix))elif start <= n:prefix.append(start)self.get_combine(res, prefix,n, k - 1, start + 1)prefix.pop()self.get_combine(res, prefix,n, k, start + 1)
上面的思路其实还是比较晦涩，下面结合运行日志理一下：
A.代表最开始固定第一位并向后寻找
前进：函数从 k = 2 , start = 1 开始，此时前缀 append 得到 [1]，这里注意，当前长度 k 和 前缀 prefix 有一个关系，即 当前长度 K + 前缀 len(prefix)= k = 2，所以当前长度 K 为0是，代表此时 len(prefix) = k = 2，即找到一个满足条件的结果，所以添加到 result
回退：当 k = 0 时，结束当前结构体，返回上一层递归，随后执行 prefix.pop 删除最后一个元素，并将 start + 1，继续向后探索，所以 prefix = [1,2] => [1]，然后 start = start + 1 = 3，此时 k=1，继续递归 start = 3 加入 prifix [1] => [1,3] ，k = 1 -> 0 继续保存，随后寻找下一个数字
B.代表固定位置的数字的所有可能遍历完毕，继续固定下一个数字
[1,2]，[1,3]，[1,4] 添加完毕后，1 的所有可能已经结束了，一直回退程序直到 prefix -> []，此时开始执行 start + 1，即前缀变为 [2]，然后固定2，往后找3，找4，随后回退直到 prefix -> []，再从3开始
C.代表任务结束
当 [3,4] 添加到结果并且 prefix pop 到 [] 时，要开始固定下一个位置，此时 k = 2，start = 5 始终 > n = 4，所以程序不再递归，直到退出并返回 res
三.全排列
1.方法思路
如果上面不好理解，其实还有偷懒的方法 : 对 1-n 的数字全排列随后截断去重，给定 n = 4, k = 2
(1) 对数组 [1,2,3,4] 全排列得到全排列全部结果:
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4],...[4, 1, 2, 3]]
(2) 随后将取全排列数组 top-k:
[[1, 2], [1, 2], [1, 3],...[4, 1]]
(3) 然后去重 "12","12","13",...,"41" 得到:
{'12', '24', '34', '23', '14', '13'}
2.实现
全排列之前介绍了几种方法在:求数组全排列中，这里给出其中一种方法，回朔法:
def solveByBackTrack(nums):def backtrack(position, end):if position == end:res.append(nums[:])returnfor index in range(position, end):nums[index], nums[position] = nums[position], nums[index]backtrack(position + 1, end)nums[index], nums[position] = nums[position], nums[index]res = []backtrack(0, len(nums))return resdef getArrangeByBackTrack(n, k):nums = list(range(1, n + 1))candidates = set() # 去重results = solveByBackTrack(nums) # 全排列for i in results:tmp = i[:k] # 截断tmp.sort()candidates.add(''.join(list(map(lambda x: str(x), tmp))))return candidates# 全排列n = 4k = 2re = getArrangeByBackTrack(n, k)print(re)
{'12', '13', '24', '14', '23', '34'}
全排列截断虽然思路清晰，但是随着 n 的增加，堆栈的递归深度和线程占用非常严重，这里仅供偷懒，不做实际使用
四.API-itertools
itertools 提供combinations 方法可以直接获取对应排列，如果不是做题而是学习工作中有需求可以直接调用该方法：
import itertoolsn = 4k = 2nums = list(range(1, n+1))can = list(binations(nums, k))print(can)
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
五.耗时
常规 n, k
n >> k
该用哪个不该用哪个很明显了吧 ~
