力扣链接:77. 组合 - 力扣（LeetCode）

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

"""
思路:
dfs + 回溯的算法逻辑
用到递归,我们就要直到递归的三个条件:
1,从哪里开始?
2,到哪里结束?
,下一个是从哪里开始?
本题是从一个nums数组中,排列出k个组合[1,2,3] -> 12,13,23
从哪里开始?我们可以遍历数组的index,从第一个索引位置开始?
哪里结束?当我们的path中有k个结果时结束,这里是组合不是排列,所以我们对结果排序,eg:12,21排序后都是12,防止把21结果加入
如果是排列,我们就不需要去排序判断结果
下一个就是i+1
"""def combine(n,k):nums = [i + 1 for i in range(4)]res = []path = []def dfs(choices):# 还要选d个数字if len(path) == k:tmp_res=sorted(path)if tmp_res not in res:res.append(tmp_res)returnfor i in range(len(choices)):path.append(choices[i])dfs(choices[:i] + choices[i+1:])path.pop()dfs(nums)return resprint(combine(4,2))

力扣链接:78. 子集 - 力扣（LeetCode）

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

"""
思路,此题和77题组合一样,但是多了一个变化的条件,既组合的元素的数量
我们还是用dfs + 回溯"""def subsets(nums):res = []path = []def dfs(choices, k):if len(path) == k:tmp_res = sorted(path)if tmp_res not in res:res.append(tmp_res)returnfor i in range(len(choices)):path.append(choices[i])dfs(choices[:i] + choices[i + 1:], k)path.pop()for k in range(len(nums) + 1):dfs(nums, k)return resprint(subsets([1, 2, 3]))