力扣鏈接: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]))