力扣（2024.06.18）

1. 39——组合总和

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

标签：数组，回溯

代码：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(candidates, target, sum, start, res, path):
            if sum == target:
                res.append(path.copy())
                return 
            for i in range(start, len(candidates)):
                if sum + candidates[i] > target:
                    break
                sum = sum + candidates[i]
                path.append(candidates[i])
                backtrack(candidates, target, sum, i, res, path)
                sum = sum - candidates[i]
                path.pop()
        res = []
        path = []
        candidates.sort()
        backtrack(candidates, target, 0, 0, res, path)
        return res

2. 40——组合总和2

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。注意：解集不能包含重复的组合。 

标签：数组，回溯

代码：

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(candidates, target, sum, start, res, path):
            if sum == target:
                res.append(path.copy())
                return
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                if sum + candidates[i] > target:
                    break
                sum = sum + candidates[i]
                path.append(candidates[i])
                backtrack(candidates, target, sum, i+1, res, path)
                sum = sum - candidates[i]
                path.pop()
        res = []
        path = []
        candidates.sort()
        backtrack(candidates, target, 0, 0, res, path)
        return res

3. 41——缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

标签：数组，哈希表

代码：

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if nums[i] <= 0 or nums[i] >= n + 1:
                nums[i] = n + 1
        for num in nums:
            idx = abs(num)
            if idx <= n and nums[idx - 1] > 0:
                nums[idx - 1] = - nums[idx - 1]
        for i in range(n):
            if nums[i] > 0:
                return i + 1
        return n + 1