力扣第77题-组合-力扣第78题-子集

发布于:2025-07-01 ⋅ 阅读:(26) ⋅ 点赞:(0)

力扣链接: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)
                return

        for i in range(len(choices)):
            path.append(choices[i])
            dfs(choices[:i] + choices[i+1:])
            path.pop()
    dfs(nums)
    return res

print(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)
                return
        for 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 res


print(subsets([1, 2, 3]))


网站公告

今日签到

点亮在社区的每一天
去签到