1 组合

数字都不同，dfs搜索：

python
展开代码
from typing import List
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(start):
            if len(sol) == k:
                res.append(sol[:])
                return
            if start == len(nums):
                return
            for i in range(start, len(nums)):
                sol.append(nums[i])
                dfs(i + 1)
                sol.pop()
        res = []
        sol = []
        nums = list(range(1, n + 1))
        dfs(0)
        return res

2 组合总和

39. 组合总和

https://leetcode-cn.com/problems/combination-sum/comments/

python
展开代码
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        temp = []
        def recursion(idx, res):
            if idx >= len(candidates) or res >= target:
                if res == target:
                    ans.append(temp[:])
                return
            temp.append(candidates[idx])
            recursion(idx, res + candidates[idx]) 
            temp.pop()
            recursion(idx + 1, res)
        recursion(0, 0)
        return ans 

python
展开代码
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(index,sol_sum,sol): # 序号，加和，选取的列表
            if sol_sum==target:
                res.append(sol[:])
                return
            if index==n or sol_sum>target:
                return
            dfs(index, sol_sum+candidates[index], sol+[candidates[index]]) # 选择上当前元素，继续搜
            dfs(index+1, sol_sum, sol) # 不选上当前元素，继续搜
        candidates.sort()
        n = len(candidates)
        res = []
        dfs(0,0,[])
        return res

python
展开代码
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(index,sol_sum,sol): # 序号，加和，选取的列表
            if sol_sum==target:
                res.append(sol[:])
                return
            if index==n or sol_sum>target:
                return
            # 解法1
            # dfs(index, sol_sum+candidates[index], sol+[candidates[index]]) # 选择上当前元素，继续搜
            # dfs(index+1, sol_sum, sol) # 不选上当前元素，继续搜
            # 解法2
            for i in range(index,n):
                sol_sum+=candidates[i]
                sol+=[candidates[i]]
                dfs(i, sol_sum, sol) # 基于此继续选择，传i，下一次就不会选到i左边的数
                sol_sum-=candidates[i]
                sol.pop()
        candidates.sort()
        n = len(candidates)
        res = []
        dfs(0,0,[])
        return res

3 组合总和2

https://leetcode-cn.com/problems/combination-sum/comments/

python
展开代码
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(pos: int, rest: int):
            nonlocal sequence
            if rest == 0:
                ans.append(sequence[:])
                return
            if pos == len(freq) or rest < freq[pos][0]:
                return
            dfs(pos + 1, rest)
            most = min(rest // freq[pos][0], freq[pos][1])
            for i in range(1, most + 1):
                sequence.append(freq[pos][0])
                dfs(pos + 1, rest - i * freq[pos][0])
            sequence = sequence[:-most]
        freq = sorted(collections.Counter(candidates).items())
        ans = list()
        sequence = list()
        dfs(0, target)
        return ans

4 子集

https://leetcode-cn.com/problems/subsets/

https://leetcode-cn.com/problems/subsets-ii/