1、题目描述
https://leetcode-cn.com/problems/combinations/
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
输入: n = 4, k = 2
输出:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]回溯
回溯-39. 组合总和 https://blog.csdn.net/IOT_victor/article/details/107646185
77.组合
40. 组合总和 II
78. 子集
90. 子集 II
https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-by-powcai-4/
2、代码详解
class Solution(object):def combine(self, n, k):""":type n: int:type k: int:rtype: List[List[int]]"""res = []def backtrack(i, k, tmp): # k个数（减至0）if k == 0:res.append(tmp)returnfor j in range(i, n + 1): # n表示从1到n中取k个数的组合backtrack(j+1, k-1, tmp + [j])backtrack(1, k, [])return reshttps://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-by-powcai-4/
题目就是要求我们从1到n找长度为k的组合数，所以回溯的终止条件就有了。
然后就是回溯的模板，但更重要的是弄清渐枝的条件,相同元素但顺序不同仍旧算为一组，那么也就是不能出现逆序。
class Solution:def combine(self, n: int, k: int) -> List[List[int]]:def back(candidates, cur):if len(cur) == k:result.append(cur[:])returnfor i in range(len(candidates)):if len(cur) > 0 and candidates[i] < cur[-1]: # 最重要是这一句实现剪枝，如果出现逆序就continuecontinuecur.append(candidates[i])back(candidates[:i] + candidates[i + 1:], cur)cur.pop()nums = [i for i in range(1, n + 1)]result = []back(nums, [])return result
https://leetcode-cn.com/problems/combinations/solution/xiong-mao-shua-ti-python3-hui-su-jian-zhi-by-lot-2/
拓展：求组合公式
def zuhe(m, n):x = 1y = 1ret = 1if m < n:returnelse:c = min(n, m-n)for i in range(c):x = x*(m-i)y = y * (c-i)ret = x//yreturn ret
m = int(input())
n = int(input())
ans = zuhe(m, n)
print(ans)
本文链接：https://my.lmcjl.com/post/8226.html
展开阅读全文
4 评论